P-Matchings Parameterized by Treewidth

Juhi Chaudhary, Meirav Zehavi

Abstract

In graph theory, while finding a maximum matching is a classic polynomial-time problem, adding structural constraints to the matching—resulting in $\mathcal{P}$-matchings—often renders the problem NP-complete. This paper investigates the complexity of three specific variants: Induced, Acyclic, and Disconnected matchings, when parameterized by the graph's treewidth ($tw$). By employing advanced algorithmic techniques such as Fast Subset Convolution and the randomized Cut & Count method, the authors establish new single-exponential upper bounds and provide a super-exponential lower bound for the general Disconnected Matching problem under the Exponential Time Hypothesis (ETH).

Introduction

A matching in a graph is a set of edges that share no common endpoints. While the basic version of this problem is computationally easy, many applications require matchings that satisfy additional structural properties. These are known as $\mathcal{P}$-matchings. This research focuses on three primary variants:

  1. Induced Matching: A matching where no two edges are connected by an additional edge in the original graph. This is equivalent to finding an independent set in the line graph's square.
  2. Acyclic Matching: A matching where the subgraph induced by the endpoints of the matching edges contains no cycles.
  3. Disconnected Matching: A matching where the subgraph induced by the matching endpoints must consist of at least $c$ connected components.

While these problems were previously known to be Fixed-Parameter Tractable (FPT) with respect to treewidth, existing algorithms were often suboptimal or relied on non-constructive logic-based proofs (like Courcelle’s Theorem) that do not yield practical running times. This paper aims to bridge the gap between theoretical tractability and algorithmic efficiency.

Algorithmic Techniques

The authors achieve their results by refining dynamic programming (DP) on tree decompositions. Several sophisticated techniques are introduced to optimize the state space and transition times.

Nice Tree Decomposition with Deferred Edges

To simplify the DP transitions, the authors utilize a modified version of "nice" tree decompositions. By deferring the introduction of edges until both endpoints are present in the bag and no further edges can be added to those vertices, they streamline the state transitions, particularly for the Induced Matching problem.

Fast Subset Convolution

The bottleneck in treewidth-based DP often occurs at "Join nodes," where solutions from two subtrees are merged. For Induced Matching, a naive merge takes $O(4^{tw})$ time. The authors reframe this join operation as a subset convolution over a max-sum semiring. By applying Fast Subset Convolution, they reduce the complexity to $O(3^{tw} \cdot tw^{O(1)} \cdot n)$, effectively breaking the $4^{tw}$ barrier.

Cut & Count for Acyclic Matchings

Acyclic Matching is particularly challenging because cycle-detection is a global property, making it difficult to track in local DP states. The authors employ the randomized "Cut & Count" method. This technique involves counting the number of ways to "cut" a solution into components while satisfying specific parity conditions. Combined with the Isolation Lemma, this allows the algorithm to detect acyclic solutions in $O(6^{tw} \cdot n^{O(1)})$ time, providing the first concrete single-exponential algorithm for this problem.

Fine Coloring for Disconnected Matchings

For the $c$-Disconnected Matching problem (where $c$ is a fixed constant), the authors introduce a "fine coloring" scheme. This method tracks component assignments without the exponential overhead of storing full partitions of the vertices in each bag, keeping the state space manageable at $O((3c)^{tw})$.

Complexity Results and Lower Bounds

The paper provides a comprehensive update to the complexity landscape of $\mathcal{P}$-matchings. The results are summarized in the table below:

Problem New Complexity Result Improvement / Note
Induced Matching $O(3^{tw} \cdot tw^{O(1)} \cdot n)$ Improved from $O(4^{tw} \cdot n)$
Acyclic Matching $O(6^{tw} \cdot n^{O(1)})$ First single-exponential (randomized)
$c$-Disconnected Matching $O((3c)^{tw} \cdot tw^{O(1)} \cdot n)$ Resolves open question for fixed $c$
Disconnected Matching No $2^{o(pw \log pw)} \cdot n^{O(1)}$ Super-exponential lower bound (under ETH)

One of the most significant theoretical contributions is the lower bound for the general Disconnected Matching problem (where $c$ is part of the input). The authors prove that if the Exponential Time Hypothesis (ETH) holds, the problem cannot be solved in $2^{o(pw \log pw)}$ time, where $pw$ is the pathwidth. This explains why a standard $2^{O(tw)}$ algorithm is likely impossible for the general case, marking a sharp contrast between fixed and variable component requirements.

Conclusion

This work significantly advances the state of the art for matching problems on bounded treewidth graphs. By moving Acyclic Matching from the realm of theoretical FPT to concrete single-exponential time and optimizing Induced Matching, the authors provide tools that are much closer to practical implementation. Future work remains in derandomizing the Acyclic Matching algorithm and investigating whether Induced Matching can be further optimized to $(3-\epsilon)^{tw}$ under the Strong Exponential Time Hypothesis (SETH).

Summary updated

BibTeX
@inproceedings{chaudhary2023p,
  author = {Juhi Chaudhary and Meirav Zehavi},
  title = {{P-Matchings Parameterized by Treewidth}},
  booktitle = {WG},
  year = {2023},
  doi = {10.1007/978-3-031-43380-1\_16},
}
Figure