מירב זהבי

A matching is a subset of edges in a graph G that do not share an endpoint. A matching M is a P-matching if the subgraph of G induced by the endpoints of the edges of M satisfies property P. For example, if the property P 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 G and a positive integer ℓ, the P Matching problem asks whether G has a P-matching of size at least ℓ. In this paper, we analyze the P 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 3^tw· tw^O(1) · n time and a randomized algorithm solving Acyclic Matching in 6^tw· tw^O(1) · n time. For any fixed c ≥ 2, c-Disconnected Matching can be solved in (3c)^tw· tw^O(1) · n time by a deterministic algorithm. Additionally, assuming the Exponential Time Hypothesis, we show that Disconnected Matching has no 2^{o(pw log pw)} · n^O(1)-time algorithm.