Modular decomposition

In graph theory, the modular decomposition is a decomposition of an undirected graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition. For each undirected graph, this decomposition is unique.

The modular decomposition can be generalized to other structures (for example directed graphs) and the development of efficient algorithms for computing it have led to efficient algorithms for a variety of combinatorial, topological, and optimization problems on graphs.

Modules

A module of a graph is a generalization of a connected component. A set X of vertices is a connected component if every member of X is a non-neighbor of every vertex not in X. More generally, X is a module if, for each vertex $v\not \in X$ , either every member of X is a non-neighbor of v or every member of X is a neighbor of v.

Equivalently, X is a module if all members of X have the same set of neighbors among vertices not in X.

Contrary to the connected components, the modules of a graph are the same as the modules of its complement, and modules can be "nested": one module can be a proper subset of another.Note that the set V of vertices of a graph, as are its one-element subsets and the empty set; these are called the trivial modules. A graph may or may not have other modules. A graph is called prime if all of its modules are trivial.

Despite these differences, modules preserve a desirable property of connected components, which is that many properties of the subgraph G[X] induced by a connected component are independent of the rest of the graph. A similar phenomenon also applies to the subgraphs induced by modules.

The modules of a graph are therefore of great algorithmic interest. A set of nested modules, of which the modular decomposition is an example, can be used to guide the recursive solution of many combinatorial problems on graphs, such as recognizing and transitively orienting comparability graphs, recognizing and finding permutation representations of permutation graphs, recognizing whether a graph is a cograph and finding a certificate of the answer to the question, recognizing interval graphs and finding interval representations for them, defining distance-hereditary graphs and for graph drawing. They play an important role in Lovasz's celebrated proof of the perfect graph theorem.

For recognizing distance-hereditary graphs and circle graphs, a further generalization of modular decomposition, called the split decomposition, is especially useful.

As the notion of modular decomposition has been rediscovered in many areas, modules have also been called autonomous sets, homogeneous sets, intervals, and partitive sets.

To avoid the possibility of ambiguity in the above definitions, we give the following formal definitions of modules. $G=(V,E)$ . $M\subseteq V$ is a module of $G$ if:

the vertices of $M$ cannot be distinguished by any vertex in $V\backslash M$ , i.e.

$\forall u,v\in M,\forall x\in V\backslash M$ , either $x$ is adjacent to both $u$ and $v$ or $x$ is not adjacent to both $u$ and $v$ .

the vertices of $M$ have the same set of outer neighbors, i.e.

$\forall u,v\in M,\{x\in V\backslash M$ adjacent to $u\}=\{x\in V\backslash M$ adjacent to $v\}$ .

Modular quotients and factors

If $X$ and $Y$ are disjoint modules, then it is easy to see that either every member of $X$ is a neighbor of every element of $Y$ , or no member of $X$ is adjacent to any member of $Y$ . Thus, the relationship between two disjoint modules is either adjacent or nonadjacent. No relationship intermediate between these two extremes can.

Because of this, modular partitions of $V$ where each partition class is a module are of particular interest. Suppose $P$ is a modular partition. Since the partition classes are disjoint, their adjacencies constitute a new graph, a quotient graph $G/P$ , whose vertices are the members of $P$ . That is, each vertex of $G/P$ is a module of G, and the adjacencies of these modules are the edges of $G/P$ .

In the figure below, vertex 1, vertices 2 through 4, vertex 5, vertices 6 and 7, and vertices 8 through 11 are a modular partition. In the upper right diagram, the edges between these sets depict the quotient given by this partition, while the edges internal to the sets depict the corresponding factors.

The partitions {V} and $\{\{x\}|x\in V\}$ are the trivial modular partitions. $G/\{V\}$ is just the one-vertex graph, while $G/\{\{x\}|x\in V\}$ = G. Suppose $X$ is a nontrivial module. Then $X$ and the one-elements subsets of $V\backslash X$ are a nontrivial modular partition of $V$ . Thus, the existence of any nontrivial modules implies the existence of nontrivial modular partitions. In general, many or all members of $P$ can be nontrivial modules.

If P is a nontrivial modular partition, then G/P is a compact representation of all the edges that have endpoints in different partition classes of P. For each partition class X in P, the subgraph G[X] induced by X is called a factor and gives a representation of all edges with both endpoints in X. Therefore, the edges of G can be reconstructed given only the quotient graph G/P and its factors. The term prime graph comes from the fact that a prime graph has only trivial quotients and factors.

When G[X] is a factor of a modular quotient G/P, it is possible that G[X] can be recursively decomposed into factors and quotients. Each level of the recursion gives rise to a quotient. As a base case, the the graph has only one vertex. Collectively, G can be reconstructed inductively by reconstructing the factors from the bottom up, inverting the steps of the decomposition by combining factors with the quotient at each level.

In the figure below, such a recursive decomposition is represented by a tree that depicts one way of recursively decomposing factors of an initial modular partition into smaller modular partitions.

A way to recursively decompose a graph into factors and quotients may not be unique. (For example, all subsets of the vertices of a complete graph are modules, which means that there are many different ways of decomposing it recursively.) Some ways may be more useful than others.

The modular decomposition

Fortunately, there exists a such a recursive decomposition of a graph that implicitly represents all ways of decomposing it; this is the modular decomposition. It is itself a way of decomposing a graph recursively into quotients, but it subsumes all others. The decomposition depicted in the figure below is this special decomposition for the given graph.

X and Y overlap if they intersect, but neither is a subset of the other. A module M is a strong module if it overlaps no other module: every other module is either disjoint from M, a subset of M, or a superset of M. A module that overlaps some other module is a weak module.

If X and Y are two strong modules, X is the parent of Y if there exists no strong module Z such that $Y\subset Z\subset X$ . This defines a tree whose nodes are the strong modules of G, which can be seen as follows. No node has two parents, since this would force the parents to overlap, contradicting that they are strong modules. Because V is a strong module, every strong module X other than V must have a parent (V or some smaller subset of V), since X is a subset of V. The parent relation is acyclic. These conditions are sufficient to make the parent relation a rooted tree, rooted at V.

Note that each node of this tree is itself a set of vertices of G.

Gallai showed that this tree can be used to give a representation of all modules of G, not just the strong ones. This is remarkable, given that the number of modules of G can be exponential in |V|, and, because they form a tree whose internal nodes each have at least two children, the number of strong modules can be at most 2|V| - 1.

The representation is obtained by the following observations.

 *Every weak module is a union of children of some node in this tree.

To see why this is the case, not that any set X other than a union of children of a node must overlap a strong module, and therefore X cannot be a module.

It therefore remains to give a mechanism for determining which unions of children of internal nodes of the tree are weak modules. For this, Gallai showed that the strong modules each fall into one of two extreme cases:

  * Degenerate:  All unions of its children are modules of G

  * Prime:  No unions of more than one and fewer than all of the children are 
    modules of G.

Therefore, the tree formed by the parent relation on strong modules, together with a labeling of its internal nodes as degenerate or prime, is what is meant by the modular decomposition. It gives an implicit representation of all modules of G. That the number of weak modules can be exponential in |V| is no longer a problem; so can the number of unions of children of a degenerate node.

A graph, a decomposition into a quotient and its corresponding factors (largest circled subgraphs),and its modular decomposition tree. In the decomposition tree, series nodes are labeled "s", parallel nodes "//" and prime nodes "p".

If G is a prime graph, its modular decomposition has as its root V, whose children are its one-element subsets, and V is labeled prime. If G is a complete graph or the complement of a complete graph, its modular decomposition is this same tree, except that V is labeled degenerate. These are the extreme cases. Other cases, such as the one in the figure, are graphs that lie somewhere between these two extremes, which gives them nontrivial modular decomposition trees.

At each internal node X of the tree, the set P of children of X are a partition of X, so G[X]/P is a modular quotient. Gallai showed that when X is a prime node, its quotient is a prime graph, and when X is a degenerate node, this quotient is either a complete graph or its complement. When the quotient is a complete graph, it is called a serial node and when it is the complement of one, it is called a parallel node.

Cographs are the graphs that only have parallel or series nodes in their modular decomposition tree.

Algorithmic issues

A data structure for representing the modular decomposition tree should support the operation that inputs a node and returns the set of vertices of G that the node represents. An obvious way to do this is to assign to each node a list of the k vertices of G that it represents. Given a pointer to a node, this structure could return the set of vertices of G that it represents in O(k) time. However, this data structure would require $\Theta (n^{2})$ space in the worst case.

An O(n)-space alternative that matches this performance is obtained by representing the modular decomposition tree using any standard O(n) rooted-tree data structure and labeling each leaf with the vertex of G that it represents. The set represented by an internal node v is given by the set of labels of its leaf descendants. It is well-known that any rooted tree with k leaves has at most k-1 internal nodes, one can using a depth-first search, starting at v, to report the labels of leaf descendants of v, takes O(k) time.

The modular decomposition, augmented with a quotient on the children of each internal node, gives a complete representation of G.

Each node X is a set of vertices of G and, if X is an internal node, the set P of children of X is a partition of X where each partition class is a module. They therefore induce the quotient G[X]/P in G[X]. The vertices of this quotient are the elements of P, so G[X]/P can be represented by installing edges among the children of X. If Y and Z are two members of P and $u\in Y$ and $v\in Z$ , then u and v are adjacent in G if and only if Y and Z are adjacent in this quotient. For any pair {u,v} of vertices of G, this is determined by the quotient at children of the least common ancestor of {u} and {v} in the modular decomposition tree. Therefore, the modular decomposition, labeled in this way with quotients, gives a complete representation of G.

Many combinatorial problems can be solved on G by solving the problem separately on each of these quotients. For example, G is a comparability graph if and only if each of these quotients is a comparability graph. A similar phenomenon applies for permutation graphs, interval graphs, and perfect graphs.

The first polynomial algorithm to compute the modular decomposition tree of a graph was published in 1972 (James, Stanton & Cowan 1972) and now linear algorithms are available (McConnell & Spinrad 1999, Tedder et al. 2007, Cournier & Habib 1994).

References

Gallai, Tibor (1967). "Transitiv orientierbare Graphen". Acta Mathematica Academiae Scientiarum Hungaricae. 18: 25‚Äì66. doi:10.1007/BF02020961. MR0221974.
James, Lee O.; Stanton, Ralph G.; Cowan, Donald D. (1972). "Graph decomposition for undirected graphs". Proc. 3rd Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1972). Florida Atlantic University. pp. 281‚Äì290. MR0351909.
McConnell, Ross M.; Spinrad, Jeremy P. (1999). "Modular decomposition and transitive orientation" (PDF). Discrete Mathematics. 201: 189‚Äì241. doi:10.1016/S0012-365X(98)00319-7. MR1687819.
Papadopoulos, Charis; Voglis, Constantinos (2006). "Drawing graphs using modular decomposition". [[International Symposium on Graph Drawing|Proc. 13th International Symposium on Graph Drawing (GD'05)]] (PDF). Lecture Notes in Computer Science. Vol. 3842. Springer-Verlag. pp. 343‚Äì354. doi:10.1007/11618058_31. MR2229205. {{cite book}}: URL–wikilink conflict (help)
Tedder, Marc; Corneil, Derek; Habib, Michel; Paul, Christophe (2008). "Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations". [[International Colloquium on Automata, Languages and Programming|Proc. 35th International Colloquium on Automata, Languages and Programming (ICALP 2008)]]. Lecture Notes in Computer Science. Vol. 5125. Springer-Verlag. pp. 634‚Äì645. doi:10.1007/978-3-540-70575-8_52. {{cite book}}: URL–wikilink conflict (help).

External links