Characterizing graphs of maximum matching width at most 2

Jisu Jeong, Seongmin Ok, Geewon Suh

Abstract

The maximum matching width (mm-width) is a width-parameter defined on a branch-decomposition over the vertex set of a graph, using the size of a maximum matching in a bipartite graph as a cut-function. This paper provides a complete characterization of graphs with maximum matching width at most 2 by identifying their minor obstruction set, which consists of 42 forbidden graphs. Furthermore, the authors determine the exact maximum matching width of a $k \times k$ grid to be $k$.

Introduction

In the realm of graph theory and computer science, width parameters serve as crucial metrics for measuring how closely a complex graph resembles a tree structure. Parameters such as treewidth and branchwidth have long been used to identify classes of graphs where NP-hard problems become computationally tractable. Maximum matching width (mm-width), introduced by Vatshelle in 2012, is a newer addition to this family. It is particularly valuable because algorithms based on mm-width can outperform treewidth-based approaches for specific problems, such as the Minimum Dominating Set.

The Minor Obstruction Set

A fundamental way to characterize graph properties that are closed under taking minors (the operations of edge deletion and contraction) is to identify the "minor obstruction set"—the set of minimal graphs that do not possess the property. While a graph with treewidth at most 2 is simply characterized by the absence of a $K_4$ minor, mm-width 2 is significantly more intricate.

The authors prove that a graph has mm-width at most 2 if and only if it does not contain any of 42 specific forbidden minors. This large set highlights the structural complexity of mm-width compared to more traditional parameters.

The complete bipartite graph $K_{3,4}$ is a prominent member of the 42-graph minor obstruction set for mm-width 2.

Methodology: Tangles and Wheels

To derive these results, the researchers utilized advanced structural tools. They employed branch-decompositions to cluster vertices and tangles to establish lower bounds on width by identifying highly connected regions that resist splitting.

A key part of the analysis involved Tutte’s Wheel Theorem, which allowed the authors to systematically examine 3-connected graphs. By analyzing how these graphs can be reduced or expanded, they identified the smallest possible obstructions. They also introduced "good-subdivisions" to construct 2-connected obstructions from smaller 3-connected components.

Wheel graphs, such as the one shown here, were analyzed via Tutte’s Wheel Theorem to identify minimal structural obstructions.

The Grid Benchmark

Grid graphs are a standard "stress test" for any new width parameter. Prior to this work, the mm-width of a $k \times k$ grid was known to be either $k-1$ or $k$. This paper definitively settles the matter, proving that for $k \ge 2$, the mm-width of a $k \times k$ grid is exactly $k$. This result demonstrates that grids are "wider" under the mm-width metric than previously estimated, providing a clear benchmark for future algorithmic analysis.

Conclusion and Algorithmic Implications

The characterization of mm-width 2 and the exact calculation for grids solidify the theoretical foundation of this parameter. Because $mmw(G) \le tw(G) + 1$, any graph with low treewidth also has low mm-width. However, mm-width can offer superior runtimes—for instance, $O^*(8^k)$ for the Dominating Set problem—making it a powerful tool for algorithm design in specific structural contexts. Future work remains to automate the discovery of obstructions for higher widths and to find more problems where mm-width provides a decisive advantage.

Summary updated

Abstract

The maximum matching width is a width-parameter that is defined on a branch-decomposition over the vertex set of a graph. The size of a maximum matching in the bipartite graph is used as a cut-function. In this paper, we characterize the graphs of maximum matching width at most 2 using the minor obstruction set. Also, we compute the exact value of the maximum matching width of a grid.
BibTeX
@inproceedings{jeong2018characterizing,
  author = {Jisu Jeong and Seongmin Ok and Geewon Suh},
  title = {{Characterizing graphs of maximum matching width at most 2}},
  booktitle = {Discret. Appl. Math},
  year = {2018},
  url = {https://openreview.net/forum?id=hqNG8yiUDH},
}
Figure