In graph theory, the modular decomposition is a decomposition of a 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.

There are variants of modular decomposition for undirected graphs and directed graphs. 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 graphs, for optimization problems on graphs, and for graph drawing.

Modules

edit

As the notion of modules has been rediscovered in many areas, modules have also been called autonomous sets, homogeneous sets, stable sets, clumps, committees, externally related sets, intervals, nonsimplifiable subnetworks, and partitive sets (Brandstädt, Le & Spinrad 1999). Perhaps the earliest reference to them, and the first description of modular quotients and the graph decomposition they give rise to appeared in (Gallai 1967).

A module of a graph is a generalization of a connected component. A connected component has the property that it is a set   of vertices such that every member of   is a non-neighbor of every vertex not in  . (It is a union of connected components if and only if it has this property.) More generally,   is a module if, for each vertex  , either every member of   is a non-neighbor of   or every member of   is a neighbor of  .

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

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   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   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 (Spinrad, 2003) and for graph drawing (Papadopoulos, 2006). They play an important role in Lovász's celebrated proof of the perfect graph theorem (Golumbic, 1980).

For recognizing distance-hereditary graphs and circle graphs, 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. Let   be a graph. A set   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 neither adjacent to   nor to  .

This condition can be succinctly written as   for all  . Here,   denotes the set of neighbours of  .

For example,  ,   and all the singletons   for   are modules. They 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  .

Modular quotients and factors

edit

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   and   are the trivial modular partitions.   is just the one-vertex graph, while  . 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   is a nontrivial modular partition, then   is a compact representation of all the edges that have endpoints in different partition classes of  . For each partition class   in  , the subgraph   induced by   is called a factor and gives a representation of all edges with both endpoints in  . Therefore, the edges of   can be reconstructed given only the quotient graph   and its factors. The term prime graph comes from the fact that a prime graph has only trivial quotients and factors.

When   is a factor of a modular quotient  , it is possible that   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,   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

edit

Fortunately, there exists 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.

 
A graph, its quotient where "bags" of vertices of the graph correspond to the children of the root of the modular decomposition tree, and its full modular decomposition tree: series nodes are labeled "s", parallel nodes "//" and prime nodes "p".

The following is a key observation in understanding the modular decomposition:

If   is a module of   and   is a subset of  , then   is a module of  , if and only if it is a module of  .

In (Gallai, 1967), Gallai defined the modular decomposition recursively on a graph with vertex set  , as follows:

  1. As a base case, if   only has one vertex, its modular decomposition is a single tree node.
  2. Gallai showed that if   is connected and so is its complement, then the maximal modules that are proper subsets of   are a partition of  . 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  . Since they are maximal, every module not represented so far is contained in a child   of  . For each child   of  , replacing   with the modular decomposition tree of   gives a representation of all modules of  , by the key observation above.
  3. If   is disconnected, its complement is connected. Every union of connected components is a module of  . All other modules are subsets of a single connected component. This represents all modules, except for subsets of connected components. For each component  , replacing   by the modular decomposition tree of   gives a representation of all modules of  , by the key observation above. The root of the tree is labeled a parallel node, and it is attached in place of   as a child of the root. The quotient defined by the children is the complement of a complete graph.
  4. If the complement of   is disconnected,   is connected. The subtrees that are children of   are defined in a way that is symmetric with the case where   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   as its leaves, due to the base case. A set   of vertices of   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  . It is in this sense that the modular decomposition tree "subsumes" all other ways of recursively decomposing   into quotients.

Algorithmic issues

edit

A data structure for representing the modular decomposition tree should support the operation that inputs a node and returns the set of vertices of   that the node represents. An obvious way to do this is to assign to each node a list of the   vertices of   that it represents. Given a pointer to a node, this structure could return the set of vertices of   that it represents in   time. However, this data structure would require   space in the worst case.

 
An   representation of the modular decomposition

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

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

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

Many combinatorial problems can be solved on   by solving the problem separately on each of these quotients. For example,   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).

Cographs 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

edit

Modular decomposition of directed graphs can be done in linear time (McConnell & de Montgolfier 2005).

With a small number of simple exceptions, every graph with a nontrivial modular decomposition also has a skew partition (Reed 2008).

References

edit
edit