\(\mathcal{P}\)-Matchings Parameterized by Treewidth
Juhi Chaudhary, Meirav Zehavi · SIAM Journal on Discrete Mathematics · 2025
Abstract. A matching is a subset of edges in a graph [Formula: see text] that do not share an endpoint. A matching [Formula: see text] is a [Formula: see text] -matching if the subgraph of [Formula: see text] induced by the endpoints of the edges of [Formula: see text] satisfies property [Formula: see text]. For example, if the property [Formula: see text] is that of being a matching, being acyclic, or being disconnected, then we obtain an induced matching, an acyclic matching, and a disconnected matching, respectively. Given a graph [Formula: see text] and a positive integer [Formula: see text], the [Formula: see text] Matching problem asks whether [Formula: see text] has a [Formula: see text]-matching of size at least [Formula: see text]. In this paper, we analyze the [Formula: see text] Matching problems from the viewpoint of Parameterized Complexity with respect to the parameter treewidth. In particular, we present a deterministic algorithm solving Induced Matching in [Formula: see text] time and a randomized algorithm solving Acyclic Matching in [Formula: see text] time. For any fixed [Formula: see text], [Formula: see text]-Disconnected Matching can be solved in [Formula: see text] time by a deterministic algorithm. Additionally, assuming the Exponential Time Hypothesis, we show that Disconnected Matching has no [Formula: see text]-time algorithm.