Modular Decomposition of graphs and digraphs

GSoC 2017, SageMath

Mentors: Dima Pasechnik, David Coudert

My name is Maria Ioanna Spyrakou and I have been working on modular decomposition of cographs and digraphs for SageMath in Google summer of code 2017.

As part of the project, I implemented in python code for:

• modular decomposition of cographs, according to [1],[2],
• a cograph generator, according to [3], and
• modular decomposition of digraphs according to [4],[5].

About Modular Decomposition

Modular decomposition represents all possible ways to decompose a graph into quotients and factors. Moreover, it is very useful tool and some of its applications include: transitive orientation, weighted maximum clique, coloring, graph drawing and many combinatorial optimization problems. Modular decomposition of a graph is a decomposition into subsets of vertices, called modules, such that every vertex of the module has uniform relationship with every other vertex outside the module. Additionally, modular decomposition of a graph can be represented as a rooted tree, where the leaves correspond to vertices and the internal nodes (more accurately: the subgraph defined by the children of each internal node) correspond to the strong modules (i.e. the modules that do not overlap any other module).

This project provides the first open-source implementation of modular decomposition of co-graphs as well as the first open-source Python implementation of modular decomposition of digraphs.

Modular Decomposition of Cographs:

Cographs (or totally decomposable graphs) are defined as the class of graphs formed from a single vertex under the closure of the operations of union and complement [1]. Equivalently cographs are the \(P_4\)-free graphs, that is the graphs that have no induced path on 4 vertices.

Every cograph has unique modular decomposition and is defined by the properties of its modular decomposition. As a result, each internal node of the cotree (i.e. modular decomposition tree of a cograph) corresponds either to union or join of subgraphs defined by the children of that node. Those nodes will be called series (node label: ‘1’) or parallel (node label: ‘0’) respectively.

Python implementation:

Github: cograph modular decomposition in Python

Given a graph in sage structure or an adjacency list of the graph, returns the modular decomposition tree (cotree), if the input graph is cograph.

Functions included:

• Cograph_modular_decomposition: if the input graph is a cograph, then construct its cotree by adding incrementally one by one its nodes. When all nodes are added the modular decomposition tree is returned. The algorithm is incremental; vertices with its adjacencies are added one by one, and the data built so far is reused, so that each vertex addition only takes \(O(deg(x))\) operations, where \(deg(x)\) is the degree of the node inserted. Hence the overall operations are \(O(|V|+|E|)\).
• Naive Cograph_recognition: (for testing purposes only) contains 3 functions that test if the input graph is a cograph, by searching if there is a \(P_4\) path on any induced subgraph on 4 vertices.

For the correctness of the code, the code was tested on all cographs with \(n\leq 16\) nodes using the output of an efficient generator for cographs.

The example includes the testing of the modular decomposition code:

• Generate all cotrees with \(n\leq 16\) nodes, using the cograph_generator.
• Find their corresponding cographs.
• Run the modular decomposition code for each cograph and test if the output matches the initial cotree.

Cograph generator:

Given the number of nodes \(n\), generates all cotrees that correspond to all cographs with \(n\) nodes. The algorithm generates one by one every cotree with n nodes, and for each cotree is generated by using its previous cotree. The time to construct the first cotree is \(O(n)\) and the time spent between two consecutive outputs is \(O(n)\). Hence, the overall complexity of the algorithm is \(O(n M_n)\) , where \(n\) is the number of nodes and \(M_n\) is the total number of cographs with n nodes. For each \(n\), the number of cographs with n nodes can be found at oeis.org/A000084 (The On-Line Encyclopedia of Integer Sequences).

Python implementation:

Github: cograph generator in Python

Modular Decomposition of Digraphs:

In the general case of directed graphs, modular decomposition is not necessarily unique. The internal nodes of modular decomposition tree can be labeled as one of the following:

• series, if the subgraph defined by the children of that node is a clique
• parallel, if its subgraph defined by the children of that node is a stable set
• order, if its subgraph defined by the children of that node is a total ordering
• prime, otherwise

Python implementation:

Github: digraph modular decomposition in Python

Given a digraph in sage structure, returns the modular decomposition tree.

I haven’t fully completed the code, but I am working on it and I will have a working implementation as soon as possible. The part of the code that is completed contains the modular decomposition of a directed graph, given a factorized permutation ([5]), as long as a part of finding the factorized permutation. So, I am still working on finishing the rest of the code of the modular decomposition algorithm and I still need to create a function that tests if the modular decomposition is computed correctly and finally to test the code on a large sample of directed graphs.

References:

[1] D. G. Corneil, Y. Perl, L. K. Stewart, A linear recognition algorithm for cographs, SIAM Journal on Computing, Vol. 14, No. 4 : pp. 926-934, 1985

[2] M. Habib, C. Paul, A Survey on Algorithmic Aspects of Modular Decomposition, Computer Science Review Volume 4, Issue 1, Pages 41-59, February 2010

[3] Á. A. Jones, F. Protti, R. R. Del-Vecchio, Cograph generation with linear delay, arXiv:1612.05827v1, 2016

[4] R. M. McConnell, F. de Montgolfier. Linear-time modular decomposition of directed graphs, Discrete Applied Mathematics, Volume 145, Issue 2, 2005

[5] C. Capelle, M. Habib, F. de Montgolfier. Graph Decompositions and Factorizing Permutations. Discrete Mathematics and Theoretical Computer Sciences 5, 2002