Modular decomposition

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.

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. Let G = (V,E) be a graph. A set 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 neither adjacent to u nor to v . This condition can be succinctly written as N(u) \setminus M = N(v) \setminus M for all u,v \in M . Here, N(u) denotes the set of neighbours of u \in V . For example, \emptyset , V and all the singletons \{v\} for v \in V are modules. They 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 . The partitions \{V\} and \{\{x\}|x \in V\} are the trivial modular partitions. G/\{V\} is just the one-vertex graph, while G/\{\{x\}|x \in V\} = G . Suppose X is a nontrivial module. Then X and the one-elements subsets of V \backslash X are a nontrivial modular partition of V . Thus, the existence of any nontrivial modules implies the existence of nontrivial modular partitions. In general, many or all members of P can be nontrivial modules. If P is a nontrivial modular partition, then G/P is a compact representation of all the edges that have endpoints in different partition classes of P . For each partition class X in P , the subgraph G[X] induced by X is called a factor and gives a representation of all edges with both endpoints in X . Therefore, the edges of G can be reconstructed given only the quotient graph G/P and its factors. The term prime graph comes from the fact that a prime graph has only trivial quotients and factors. When G[X] is a factor of a modular quotient G/P , it is possible that G[X] 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, G 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.

Algorithmic issues

A data structure for representing the modular decomposition tree should support the operation that inputs a node and returns the set of vertices of G that the node represents. An obvious way to do this is to assign to each node a list of the k vertices of G that it represents. Given a pointer to a node, this structure could return the set of vertices of G that it represents in \mathcal{O}(k) time. However, this data structure would require \Theta(n^2) space in the worst case. An \mathcal{O}(n) -space alternative that matches this performance is obtained by representing the modular decomposition tree using any standard \mathcal{O}(n) rooted-tree data structure and labeling each leaf with the vertex of G that it represents. The set represented by an internal node v is given by the set of labels of its leaf descendants. It is well known that any rooted tree with k leaves has at most k-1 internal nodes. One can use a depth-first search starting at v to report the labels of leaf-descendants of v in \mathcal{O}(k) time. Each node X is a set of vertices of G and, if X is an internal node, the set P of children of X is a partition of X where each partition class is a module. They therefore induce the quotient G[X]/P in G[X] . The vertices of this quotient are the elements of P , so G[X]/P can be represented by installing edges among the children of X . If Y and Z are two members of P and u \in Y and v \in Z , then u and v are adjacent in G if and only if Y and Z are adjacent in this quotient. For any pair \{u,v\} of vertices of G , this is determined by the quotient at children of the least common ancestor of \{u\} and \{v\} in the modular decomposition tree. Therefore, the modular decomposition, labeled in this way with quotients, gives a complete representation of G . Many combinatorial problems can be solved on G by solving the problem separately on each of these quotients. For example, G 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

Modular decomposition of directed graphs can be done in linear time . With a small number of simple exceptions, every graph with a nontrivial modular decomposition also has a skew partition .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1319725757 under CC BY-SA 4.0; modifications have been made.