Algorithmic aspects of switch cographs

Vincent Cohen-Addad, Michel Habib, Fabien de MontgolfierDiscret. Appl. Math 2016 · DOI

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.

The switch operation transforms edge relationships, facilitating the reduction of complex graphs into decomposable structures.

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.

An illustration of the structural requirements for an involution module, showing how vertices $u$ and $v$ relate to external vertices $a$ and $b$ through specific mappings.

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

BibTeX
@article{cohenaddad2016algorithmic,
  author = {Vincent Cohen-Addad and Michel Habib and Fabien de Montgolfier},
  title = {{Algorithmic aspects of switch cographs}},
  journal = {Discret. Appl. Math.},
  year = {2016},
  doi = {10.1016/j.dam.2015.07.008},
}
Figure