Parameterized Results on Acyclic Matchings with Implications for Related Problems

DOI10.1007/978-3-031-43380-1_15arXiv2307.05446OpenAlexW4386974189MaRDI QIDQ6443352

Meirav Zehavi, Juhi Chaudhary

Publication date: 11 July 2023

Abstract: A matching $M$ in a graph $G$ is an emph{acyclic matching} if the subgraph of $G$ induced by the endpoints of the edges of $M$ is a forest. Given a graph $G$ and a positive integer $ell$, Acyclic Matching asks whether $G$ has an acyclic matching of size (i.e., the number of edges) at least $ell$. In this paper, we first prove that assuming $mathsfW[1]subseteqFPT$, there does not exist any $mathsfFPT$-approximation algorithm for Acyclic Matching that approximates it within a constant factor when the parameter is the size of the matching. Our reduction is general in the sense that it also asserts $mathsfFPT$-inapproximability for Induced Matching and Uniquely Restricted Matching as well. We also consider three below-guarantee parameters for Acyclic Matching, viz. $fracn2-ell$, $mathsfMM(G)-ell$, and $mathsfIS(G)-ell$, where $n$ is the number of vertices in $G$, $mathsfMM(G)$ is the matching number of $G$, and $mathsfIS(G)$ is the independence number of $G$. Furthermore, we show that Acyclic Matching does not exhibit a polynomial kernel with respect to vertex cover number (or vertex deletion distance to clique) plus the size of the matching unless $mathsfNPsubseteqmathsfcoNPslashmathsfpoly$.

Full work available at URL: https://doi.org/10.1007/978-3-031-43380-1_15

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (3)

On the complexity of minimum maximal acyclic matchings ⋮ Minimum maximal acyclic matching in proper interval graphs ⋮ Parameterized results on acyclic matchings with implications for related problems

This page was built for publication: Parameterized Results on Acyclic Matchings with Implications for Related Problems