Introduction
Graph decomposition is a cornerstone of efficient algorithm design, often serving as the "divide and conquer" engine for solving complex problems. A classic example is modular decomposition, which identifies sets of vertices (modules) that interact uniformly with the rest of the graph. This technique is exceptionally powerful for cographs, allowing NP-complete problems to be solved in linear time.
However, modular decomposition is limited; many graphs lack non-trivial modules, rendering the technique inapplicable. This paper addresses this gap by introducing involution modules, a broader decomposition framework that preserves the benefits of a unique, linear-sized tree representation while capturing a much wider variety of graph structures.
Methodology: The Switch Operator and Involution Modules
The core innovation of this work is the integration of a switch operator into the decomposition process. This operator generalizes the well-known Seidel Switch, which effectively "flips" the relationships of a vertex—turning edges into non-edges and vice versa. The authors extend this concept to 2-structures, where edges can have multiple colors, allowing for more nuanced structural transformations.
Building on this, the authors define involution modules. Unlike standard modules, which require identical relationships to external vertices, involution modules allow for relationships that are equivalent under the switch operator.
The authors prove that the family of involution modules forms a "partitive crossing family," a mathematical property that guarantees the existence of a unique, polynomial-sized decomposition tree. They provide an $O(n^2)$ algorithm to construct this tree, which then serves as the backbone for a bottom-up dynamic programming framework.
Defining Switch Cographs
The paper identifies a new class of graphs called switch cographs—those that can be completely decomposed using involution modules. This class possesses several remarkable properties:
- Forbidden Subgraphs: A graph is a switch cograph if and only if it does not contain four specific induced subgraphs: the Bull, the Gem, the Co-Gem, and the $C_5$ (a 5-vertex cycle).
- Low Clique-Width: Switch cographs are shown to have a clique-width of at most 4. This is a critical finding, as many problems that are NP-hard on general graphs become tractable on graphs with low, fixed clique-width.
Key Algorithmic Results
By leveraging the involution modular decomposition tree, the authors provide the first polynomial-time algorithms for several notoriously difficult problems. The table below summarizes the improvements in algorithmic complexity:
| Problem | Previous Status | New Complexity (Our Contribution) |
|---|---|---|
| Maximum Clique | Polynomial | $O(n + m)$ (Linear) |
| Maximum Cut | Unknown | $O(n^4)$ |
| Vertex Separator | Unknown | $O(n^8)$ |
| Vertex Cover | Polynomial | $O(n + m)$ (Linear) |
| Clique-Width | 16 | 4 |
| Recognition | Polynomial | $O(n + m)$ (Linear) |
Notably, the Maximum Cut and Vertex Separator problems are NP-complete for general graphs; their complexity for this specific class was previously unknown.
Conclusion and Future Directions
The introduction of involution modules provides a powerful new tool for graph theory. While this work successfully tackles several open problems for switch cographs, it also opens new avenues for research. Future work includes determining the complexity of the path cover problem for this class and investigating the authors' conjecture that computing treewidth for switch cographs remains NP-complete, despite their low clique-width.
Summary updated