Modular decomposition

From Wikipedia, the free encyclopedia

In graph theory, modular decomposition is the mapping of an undirected graph into a tree with three types of vertices, labeled by subsets of vertices of the graph called modules.

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, transitive orientation, optimization problems, or graph drawing.

Contents

[edit] Modules

As the notion of modular decomposition has been rediscovered in many areas, modules have also been called autonomous sets, homogeneous sets, intervals, partitive sets, etc.

We give two equivalent definitions of a module in an undirected graph G = (V,E). M \subseteq V is a module of G if:

  • the vertices of M cannot be distinguished by any vertex in V \backslash M, i.e.

\forall u,v \in M, \forall x\in V \backslash M, either x is adjacent to both u and v or x is not adjacent to both u and v.

  • the vertices of M have the same set of outer neighbors, i.e.

\forall u,v \in M, \{x \in V \backslash M adjacent to u\} =\{x \in V \backslash M adjacent to v}.

\emptyset, V and all the singletons {v} for v \in V are modules, and are called trivial modules. A graph is prime if all its modules are trivial. Connected components of a graph G, or of its complement graph are also modules of G.

M is a strong module of a graph G if it does not overlap any other module of G: \forall M' module of G, either M \cap M' = \emptyset or M \subseteq M' or M' \subseteq M.


[edit] Modular decomposition tree

A graph, its simpler representation where "bags" of nodes correspond to its strong modules, and its modular decomposition tree: series nodes are labeled "s", parallel nodes "//" and prime nodes "p".
A graph, its simpler representation where "bags" of nodes correspond to its strong modules, and its modular decomposition tree: series nodes are labeled "s", parallel nodes "//" and prime nodes "p".

The strong modules of a graph G can be organized in a tree to represent their inclusion order, that is a module M will be an ancestor of another module in the tree if M contains this module. This tree is called the modular decomposition tree of G, its root is V and its leaves are the singletons {v}, for v \in V.

The modular decomposition theorem (Gallai 1967) shows that there are exactly three types of vertices in the modular decomposition tree. For each vertex vM of the tree labeled by the module M, exactly one of the following conditions is true:

  • the subgraph of G induced by M, G[M], is not connected, then vM is called a series node, and its children are the connected components of G[M].
  • the subgraph of the complement of G induced by M, \overline{G}[M], is not connected, then vM is called a parallel node, and its children are the connected components of \overline{G}[M].
  • both G[M] and \overline{G}[M] are connected, then vM is called a prime node, and its children are labeled by the maximal strong modules included in M, which define a partition of M.

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

[edit] References

  • Gallai, Tibor (1967). "Transitiv orientierbare Graphen". Acta Mathematica Academiae Scientiarum Hungaricae 18: 25–66. doi:10.1007/BF02020961. MR0221974. 
  • James, Lee O.; Stanton, Ralph G.; Cowan, Donald .D (1972). "Graph decomposition for undirected graphs". Proceedings of the third Southeastern International Conference on Combinatorics, Graph Theory, and Computing (CGTC'72): 281–290. MR0351909. 

[edit] External links