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.
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.
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