Modular Decomposition - 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 (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 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 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 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 (Papadoupoulos, 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. . 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 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 .