Modular Decomposition - The Modular Decomposition

The Modular Decomposition

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.

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.

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

1. As a base case, if G only has one vertex, its modular decomposition is a single tree node.
2. 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 gives a representation of all modules of G, by the key observation above.
3. 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 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.
4. 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.