Modular decomposition

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.

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 similar phenomenon also applies to the subgraphs induced by modules.

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).

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.

is a compact representation of all the edges that have endpoints in different partition classes of

is called a factor and gives a representation of all edges with both endpoints in

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.)

It is itself a way of decomposing a graph recursively into quotients, but it subsumes all others.

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

, as follows: The final tree has one-element sets of vertices of

It is in this sense that the modular decomposition tree "subsumes" all other ways of recursively decomposing

A data structure for representing the modular decomposition tree should support the operation that inputs a node and returns the set of vertices of

Given a pointer to a node, this structure could return the set of vertices of

-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

, this is determined by the quotient at children of the least common ancestor of

Therefore, the modular decomposition, labeled in this way with quotients, gives a complete representation of

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).

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).

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).