Source-linked AI summary
A survey on algorithmic aspects of modular decomposition
Michel Habib, Christophe Paul
TL;DR
Modular decomposition spans multiple discrete structures and supports structural graph theory and optimization, motivating efficient computation of its decomposition tree. This survey synthesizes the field’s algorithmic ideas, including cograph recognition, partition refinement, skeleton methods, and factoring permutations, while identifying certification and bottleneck limitations.
Problem
Modular decomposition is broadly useful, but its algorithmic development across graph and related discrete-structure applications requires synthesis.
Method
The paper surveys algorithmic theory through partitive families, cographs, partition refinement, modular decomposition algorithms, and factoring permutations.
Results
The surveyed algorithms progress from O(n^4) to cubic, quadratic, and linear running times, while cographs admit linear-time recognition.
Takeaways & Limitations
The survey identifies algorithmic techniques developed for modular decomposition that may be useful in other applications or computer-science topics.
Takeaways & Limitations
A simple linear-time certifying algorithm remains open, with certification of prime-node labels as the bottleneck.
Abstract
from arXiv · showhide
The modular decomposition is a technique that applies but is not restricted to graphs. The notion of module naturally appears in the proofs of many graph theoretical theorems. Computing the modular decomposition tree is an important preprocessing step to solve a large number of combinatorial optimization problems. Since the first polynomial time algorithm in the early 70's, the algorithmic of the modular decomposition has known an important development. This paper survey the ideas and techniques that arose from this line of research.
1 Introduction
Modular decomposition applies across several discrete structures and supports structural graph theory and optimization. This survey traces the development of its algorithmic techniques, from early polynomial-time methods to linear-time approaches.
- Modular decomposition applies to graphs, 2-structures, hypergraphs, set systems, and matroids.
- Modules support structural results in comparability and perfect graph theory and characterize several graph classes through their decomposition trees.
- The modular decomposition tree can serve as preprocessing for optimization problems on graphs and other discrete structures.
- Algorithmic progress advanced from an O(n^4) algorithm through cubic and quadratic time to independent linear-time algorithms in 1994.
- The survey presents partitive-family theory, cographs, partition refinement, modular decomposition algorithms, and factoring permutations.
2 Partitive families
Partitive-family theory provides a compact tree representation for families with closure properties, while graph modules form a partitive family. Modular partitions and quotient graphs expose the recursive structure used in modular decomposition.
- The modular decomposition theory is presented as a special case of partitive-family theory applicable to graphs, matroids, and hypergraphs.
- The strong-element tree represents a partitive family: every family member is strong or is a union of children of a degenerate strong element.
- Although a partitive family may be exponentially large, its strong elements yield a representation linear in the size of the ground set.
- A factoring permutation orders elements so every strong family element appears consecutively, linking permutations to strong-element trees.
- A graph module has uniform adjacency to every outside vertex, and the family of graph modules is partitive.
- A modular partition consists of graph modules whose quotient graph represents adjacency between the partition parts.
3 Cographs recognition algorithms as an appetizer
The survey presents cographs as an algorithmic appetizer: cotrees support linear recognition and localized updates under vertex or edge modifications. These results lead to fully dynamic maintenance whose cost depends on the modification size.
- Adding a vertex to a cograph: The vertex-incremental algorithm builds a cograph’s cotree by adding vertices one at a time, while testing insertion through cotree node labels.Nodes are labelled according to whether their modules are empty, adjacent, or mixed relative to the new vertex’s neighborhood.
- Adding a vertex to a cograph: A cograph insertion is valid when either no cotree node is mixed or the mixed nodes form a root-to-insertion-node path satisfying series and parallel child conditions.For series nodes away from the insertion node, all children must be adjacent; for parallel nodes, all must be empty.
- Adding a vertex to a cograph: The insertion process labels the cotree bottom-up in O(|S|) time, and testing the validity conditions has the same complexity.The marked nodes correspond to the relevant path when the augmented graph remains a cograph.
- Edge modification algorithms for cographs: Cographs can be recognized in linear time, and edge or vertex modifications can be handled by local cotree updates.For edge insertion, the relevant cotree structure changes only locally when the resulting graph remains a cograph.
- Edge modification algorithms for cographs: An algorithm maintains the modular decomposition tree of a cograph in O(d) time per edge or vertex insertion and deletion, where d is the number involved in the modification.This is described as a fully-dynamic algorithm.
- Related developments: The cograph techniques connect to broader incremental and dynamic decomposition results for general graphs and other graph classes.Related developments include quadratic modular decomposition, newer recognition algorithms, and fully dynamic representations for permutation and interval graphs.
4 Partition refinement
Partition refinement repeatedly splits parts using pivot sets until they become stable, providing a powerful route to modular partitions. With Hopcroft’s rule, the presented algorithm computes the coarsest modular partition in O(n + m log n) time.
- Data-structures and algorithmic scheme: Partition refinement repeatedly applies a split operation to obtain the coarsest partition refining the current partition and stable for a pivot set.A part X is split into X ∩ S and X \ S when both are nonempty.
- Data-structures and algorithmic scheme: The standard partition data structure stores vertices in consecutive doubly linked-list intervals, with pointers from vertices to their parts and from parts to their endpoints.This representation supports efficient construction of the parts intersecting a pivot set.
- Data-structures and algorithmic scheme: Refine(P, S) runs in O(|S|) time, and refinement by S is equivalent to refinement by its complement.This equivalence allows algorithms to handle graph complements without explicitly storing the complement’s edge set.
- Hopcroft’s rule and computation of a modular partition: O(n + m log n) is the running time for computing the coarsest modular partition of a graph relative to an input vertex partition.Correctness is supported by invariants preserving contained modules, identifying extracted modules, and exposing splitters for nonmodules.
- Hopcroft’s rule and computation of a modular partition: The modular-partition algorithm refines parts using vertex neighborhoods until every part is a module, while Hopcroft’s rule avoids repeatedly pivoting through the largest part.Only one vertex from the avoided largest part is needed as a pivot, preserving the needed stability properties.
- Hopcroft’s rule and computation of a modular partition: The algorithm manages parts in two lists: all vertices of parts in L contribute neighborhoods, whereas K uses one selected vertex per part.The FIFO handling of K ensures that the first extracted part is a module when L is empty.
5 Recursive computation of the modular decomposition tree
The skeleton algorithm recursively reconstructs the modular decomposition tree from a v-modular partition, a spine, and induced subgraphs. Its main technical bottleneck is computing the spine, while later variants improve the quadratic complexity.
- Skeleton algorithm: The skeleton algorithm first computes spine(G, v), recursively decomposes induced subgraphs for modules in M(G, v), and pads those trees to the spine.This procedure is applied to 2-structures as well as graphs.
- Skeleton algorithm: M(G, v) consists of v and the maximal modules not containing v, and spine(G, v) is MD(G/M(G, v)).The partition is the coarsest modular partition for G and {N(v), v, N̄(v)}, computable in O(n + m log n).
- Complexity: Computing spine(G, v) is the skeleton algorithm’s main complexity bottleneck; the original approach is quadratic, while later versions achieve O(n + m·α(n, m)) or linear time.The improved algorithms recursively decompose the subgraphs induced by N(v) and N̄(v) to retrieve M(G, v).
- Skeleton algorithm: The quotient graph G/M(G, v) is nested with inner vertex v, so every non-trivial module in the quotient contains v.Any module not containing v is contained in one part of M(G, v).
- Computing the spine: The forcing graph encodes containment: vertices reachable from x, together with v, form the smallest module containing v and x.Its arcs ensure that reached vertices belong to every module containing v and x.
- Computing the spine: Strongly connected components of the forcing graph form blocks whose transitive-reduction block graph is a chain; sink sets identify quotient modules and determine the spine.The final decomposition tree is obtained recursively using the structural properties of the v-modular partition.
6 Factoring permutation algorithm
The factoring-permutation approach separates computing an ordering from reconstructing the modular decomposition tree. Partition refinement computes the ordering efficiently, and fracture-based traversals then recover and clean an approximate decomposition tree.
- Overview: Computing a modular decomposition tree and computing a factoring permutation are equivalent tasks, with either recoverable from the other in linear time.This divides decomposition into ordering computation followed by tree reconstruction.
- Computing a factoring permutation: The algorithm computes an ordered modular partition in which strong modules containing v are intervals, then recursively computes factoring permutations for each induced module.The initial ordered partition is [N(v), {v}, N̄(v)].
- Computing a factoring permutation: Algorithm 4 computes a factoring permutation in O(n + m log n) time using partition refinement.Its correctness maintains the invariant that every strong module containing v remains an interval of the current partition.
- Cographs: For cographs, refinement can use at most one pivot per partition part, supporting a linear-time factoring-permutation algorithm.The general log n factor reflects how often vertex neighbourhoods refine the partition.
- Reconstructing the tree: Given a factoring permutation, fractures of consecutive vertex pairs define a parenthesis system and a fracture tree computable by two traversals.Left and right fractures are determined by the nearest splitters on either side of each consecutive pair.
- Reconstructing the tree: The fracture tree represents prime strong modules whose parent is degenerate, but it must be cleaned to recover the full modular decomposition tree.Four additional traversals identify represented modules, dummy nodes, merged modules, and nodes that are not strong modules.
7 Three novel applications of the modular decomposition
The survey presents modular decomposition applications in permutation pattern matching, comparative genomics, and parameterized kernelization. Across these applications, strong intervals or modules provide structures for linear-time computation, perfect reversal scenarios, and reduction rules.
- 7 Three novel applications of the modular decomposition: Modular decomposition supports applications across discrete structures, including pattern matching, comparative genomics, and module-based data reduction for parameterized problems.The survey presents these as three applications of the broader modular decomposition framework.
- 7.1 Pattern matching - common intervals of two permutations: Common intervals of two permutations are organized into a strong interval tree, supporting pattern-matching applications and links to modular decomposition.The family of common intervals is weakly partitive, and its strong members form a tree.
- 7.1 Pattern matching - common intervals of two permutations: O(n + K) time enumerates all common intervals of two permutations, where K is their possibly quadratic number.Uno and Yagiura’s algorithm traverses the permutation once and uses splitter counts to filter candidate boundaries.
- 7.1 Pattern matching - common intervals of two permutations: A set of vertices is a strong module of a permutation graph iff it is a strong common interval in the graph’s realizer permutations.The strong interval tree of the realizer is isomorphic to the graph’s modular decomposition tree.
- 7.2 Comparative genomic - perfect sorting by reversals: Common intervals model conserved chromosomal structures, and perfect reversal scenarios are characterized by prime intervals or unions of strong intervals under prime nodes.The genomic motivation comes from signed-permutation models in which shared gene content may reflect ancestral conserved structure.
8 Conclusions and perspectives
The survey identifies unresolved challenges in certifying modular decompositions, maintaining them dynamically in general graphs, and extending modules approximately while retaining polynomial tractability.
- 8 Conclusions and perspectives: A simple linear-time certifying algorithm remains open because certifying prime-node labels is the bottleneck.The decomposition tree itself can be checked in linear time, but establishing that it is the modular decomposition requires certifying every node label.
- 8 Conclusions and perspectives: Fully dynamic modular decomposition remains an open problem for general graphs, although related algorithms exist for cographs, permutation graphs, and interval graphs.The survey describes cograph principles and geometric-representation approaches for the other two graph classes.
- 8 Conclusions and perspectives: Finding a polynomially tractable notion of approximate module is difficult because many natural extensions are NP-complete.Several attempts to extend modules are noted, but the survey identifies tractability as the main difficulty.