2023/07/11 by Chaudhary, Juhi, Zehavi, Meirav · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2307.05446
A matching M in a graph G is an 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 ℓ, Acyclic Matching asks whether G has an acyclic matching of size (i.e., the number of edges) at least ℓ. In this paper, we first prove that assuming W[1]\nsubseteq FPT, there does not exist any FPT-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 FPT-inapproximability for Induced Matching and Uniquely Restricted Matching as well. We also consider three below-guarantee parameters for Acyclic Matching, viz. (n)/(2)-ℓ, MM(G)-ℓ, and IS(G)-ℓ, where n is the number of vertices in G, MM(G) is the matching number of G, and IS(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 NP\subseteqcoNP\slashpoly.