Parameterized Results on Acyclic Matchings with Implications for Related Problems

DOI10.1007/978-3-031-43380-1_15MaRDI QIDQ6443352zbMATH OpenOpenAlexFDO

Authors Juhi Chaudhary, Meirav Zehavi

Publication date 11 July 2023

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)

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

Recommendations

• Parameterized results on acyclic matchings with implications for related problems
• On the parameterized complexity of the acyclic matching problem
• Acyclic matching in some subclasses of graphs
• Acyclic Matching in Some Subclasses of Graphs
• Acyclic matchings in graphs of bounded maximum degree

Cited in

(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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6443352)