Modular decomposition
Encyclopedia
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.
This notion can be generalized to other structures (for example directed graphs) and is useful to design efficient algorithms for the recognition of some graph classes, for finding transitive orientations of comparability graph
s, for optimization problems
on graphs, and for graph drawing
.
1967).
A module of a graph is a generalization of a connected component
. A connected component has the property that it is a set X of vertices such that every member of X is a non-neighbor
of every vertex not in X. (It is a union of connected components if and only if it has this property.) More generally, X is a module if, for each vertex
, 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 is a module, 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 X 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 graph
s, recognizing and finding permutation representations of permutation graph
s, recognizing whether a graph is a cograph
and finding a certificate of the answer to the question, recognizing interval graph
s and finding interval representations for them, defining distance-hereditary graph
s (Spinrad, 2003) and for graph drawing
(Papadoupoulos, 2006). They play an important role in Lovasz's celebrated proof of the perfect graph theorem (Golumbic, 1980).
For recognizing distance-hereditary graphs and circle graph
s, a further generalization of modular decomposition, called the split decomposition, is especially useful (Spinrad, 2003).
To avoid the possibility of ambiguity in the above definitions, we give the following formal definitions of modules.
.
is a module of 
if:
, either 
is adjacent to both 
and 
or 
is not adjacent to both 
and 
.
.
, 
and all the singletons 
for 
are modules, and are called trivial modules. A graph is prime if all its modules are trivial. Connected components
of a graph
, or of its complement graph are also modules of 
.
is a strong module of a graph 
if it does not overlap any other module of 
:
module of 
, either 
or 
or 
.
and 
are disjoint modules, then it is easy to see that either every member of 
is a neighbor of every element of 
, or no member of 
is adjacent to any member of 
. Thus, the relationship between two disjoint modules is either adjacent or nonadjacent. No relationship intermediate between these two extremes can exist.
Because of this, modular partitions of
where each partition class is a module are of particular interest. Suppose 
is a modular partition. Since the partition classes are disjoint, their adjacencies constitute a new graph, a quotient graph 
, whose vertices are the members of 
. That is, each vertex of 
is a module of G, and the adjacencies of these modules are the edges of 
.
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
are the trivial modular partitions. 
is just the one-vertex graph, while 
= G. Suppose 
is a nontrivial module. Then 
and the one-elements subsets of 
are a nontrivial modular partition of 
. Thus, the existence of any nontrivial modules implies the existence of nontrivial modular partitions. In general, many or all members of 
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 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 following is a key observation in understanding the modular decomposition:
If X is a module of G and Y is a subset of X, then Y is a module of G, if and only if it is a module of G[X].
In (Gallai, 1967), Gallai defined the modular decomposition recursively on a graph with vertex set V, as follows:
The final tree has one-element sets of vertices of G as its leaves, due to the base case. A set Y of vertices of G is a module if and only if it is a node of the tree or a union of children of a series or parallel node. This implicitly gives all modular partitions of V. It is in this sense that the modular decomposition tree "subsumes" all other ways of recursively decomposing G into quotients.
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.
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
and 
, 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 (Gallai, 67; Möhring, 85). Therefore, to find whether a graph is a comparability graph, one need only find whether each of the quotients is. In fact, to find a transitive orientation
of a comparability graph, it suffices to transitively orient each of these quotients of its modular decomposition (Gallai, 67; Möhring, 85). A similar phenomenon applies for permutation graphs, (McConnell and Spinrad '94), interval graphs (Hsu and Ma '99), perfect graphs, and other graph classes. Some important combinatorial optimization problems on graphs can be solved using a similar strategy (Möhring, 85).
Cograph
s are the graphs that only have parallel or series nodes in their modular decomposition tree.
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).
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
, 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
Connected component (graph theory)
In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three connected components...
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.
This notion can be generalized to other structures (for example directed graphs) and is useful to design efficient algorithms for the recognition of some graph classes, for finding transitive orientations of comparability graph
Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...
s, for optimization problems
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
on graphs, and for graph drawing
Graph drawing
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...
.
Modules
As the notion of modules has been rediscovered in many areas, modules have also been called autonomous sets, homogeneous sets, intervals, and partitive sets. Perhaps the earliest reference to them, and the first description of modular quotients and the graph decomposition they give rise to appeared in (GallaiTibor Gallai
Tibor Gallai was a Hungarian mathematician. He worked in combinatorics, especially in graph theory, and was a lifelong friend and collaborator of Paul Erdős. He was a student of Dénes König and an advisor of László Lovász...
1967).
A module of a graph is a generalization of a connected component
Connected component (graph theory)
In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three connected components...
. A connected component has the property that it is a set X of vertices such that every member of X is a non-neighbor
Neighbourhood (graph theory)
In graph theory, an adjacent vertex of a vertex v in a graph is a vertex that is connected to v by an edge. The neighbourhood of a vertex v in a graph G is the induced subgraph of G consisting of all vertices adjacent to v and all edges connecting two such vertices. For example, the image shows a...
of every vertex not in X. (It is a union of connected components if and only if it has this property.) More generally, X is a module if, for each vertex
, 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
Complement graph
In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...
, and modules can be "nested": one module can be a proper subset of another. Note that the set V of vertices of a graph is a module, 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 X 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 graph
Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...
s, recognizing and finding permutation representations of permutation graph
Permutation graph
In areas of mathematics influenced by graph theory, a permutation graph is the intersection graph of a family of line segments that connect two parallel lines in the Euclidean plane...
s, recognizing whether a graph is a cograph
Cograph
In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union...
and finding a certificate of the answer to the question, recognizing interval graph
Interval graph
In graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...
s and finding interval representations for them, defining distance-hereditary graph
Distance-hereditary graph
In graph-theoretic mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph...
s (Spinrad, 2003) and for graph drawing
Graph drawing
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...
(Papadoupoulos, 2006). They play an important role in Lovasz's celebrated proof of the perfect graph theorem (Golumbic, 1980).
For recognizing distance-hereditary graphs and circle graph
Circle graph
In graph theory, a circle graph is the intersection graph of a set of chords of a circle. That is, it is an undirected graph whose vertices can be associated with chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other.-Algorithmic...
s, a further generalization of modular decomposition, called the split decomposition, is especially useful (Spinrad, 2003).
To avoid the possibility of ambiguity in the above definitions, we give the following formal definitions of modules.
. is a module of if:
- the vertices of
cannot be distinguished by any vertex in 
, i.e.
, either is adjacent to both and or is not adjacent to both and .
- the vertices of
have the same set of outer neighbors, i.e.
., and all the singletons for are modules, and are called trivial modules. A graph is prime if all its modules are trivial. Connected componentsConnected component (graph theory)
In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three connected components...
of a graph
, or of its complement graph are also modules of . is a strong module of a graph if it does not overlap any other module of : module of , either or or .Modular quotients and factors
If and are disjoint modules, then it is easy to see that either every member of is a neighbor of every element of , or no member of is adjacent to any member of . Thus, the relationship between two disjoint modules is either adjacent or nonadjacent. No relationship intermediate between these two extremes can exist.Because of this, modular partitions of
where each partition class is a module are of particular interest. Suppose is a modular partition. Since the partition classes are disjoint, their adjacencies constitute a new graph, a quotient graph , whose vertices are the members of . That is, each vertex of is a module of G, and the adjacencies of these modules are the edges of .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
are the trivial modular partitions. is just the one-vertex graph, while = G. Suppose is a nontrivial module. Then and the one-elements subsets of are a nontrivial modular partition of . Thus, the existence of any nontrivial modules implies the existence of nontrivial modular partitions. In general, many or all members of 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 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.The following is a key observation in understanding the modular decomposition:
If X is a module of G and Y is a subset of X, then Y is a module of G, if and only if it is a module of G[X].
In (Gallai, 1967), Gallai defined the modular decomposition recursively on a graph with vertex set V, as follows:
- As a base case, if G only has one vertex, its modular decomposition is a single tree node.
- Gallai showed that if G is connected and so is its complement, then the maximal modules that are proper subsets of V are a partition of V. They are therefore a modular partition. The quotient that they define is prime. The root of the tree is labeled a prime node, and these modules are assigned as children of V. Since they are maximal, every module not represented so far is contained in a child X of V. For each child X of V, replacing X with the modular decomposition tree of G[X] gives a representation of all modules of G, by the key observation above.
- If G is disconnected, its complement is connected. Every union of connected components is a module of G. All other modules are subsets of a single connected component. This represents all modules, except for subsets of connected components. For each component X, replacing X by the modular decomposition tree of G[X] gives a representation of all modules of G, by the key observation above. The root of the tree is labeled a parallel node, and it is attached in place of X as a child of the root. The quotient defined by the children is the complement of a complete graph.
- If the complement of G is disconnected, G is connected. The subtrees that are children of V are defined in a way that is symmetric with the case where G is disconnected, since the modules of a graph are the same as the modules of its complement. The root of the tree is labeled a serial node, and the quotient defined by the children is a complete graph.
The final tree has one-element sets of vertices of G as its leaves, due to the base case. A set Y of vertices of G is a module if and only if it is a node of the tree or a union of children of a series or parallel node. This implicitly gives all modular partitions of V. It is in this sense that the modular decomposition tree "subsumes" all other ways of recursively decomposing G into quotients.
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 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.
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
and , 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 (Gallai, 67; Möhring, 85). Therefore, to find whether a graph is a comparability graph, one need only find whether each of the quotients is. In fact, to find a transitive orientation
Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...
of a comparability graph, it suffices to transitively orient each of these quotients of its modular decomposition (Gallai, 67; Möhring, 85). A similar phenomenon applies for permutation graphs, (McConnell and Spinrad '94), interval graphs (Hsu and Ma '99), perfect graphs, and other graph classes. Some important combinatorial optimization problems on graphs can be solved using a similar strategy (Möhring, 85).
Cograph
Cograph
In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union...
s are the graphs that only have parallel or series nodes in their modular decomposition tree.
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).
Generalizations
Modular decomposition of directed graphs can be done in linear time .External links
- A bibliography of modular decomposition algorithms
- A PerlPerlPerl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
implementation of a modular decomposition algorithm - A Java implementation of a modular decomposition algorithm