A matching Min 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 l is an element of N, ACYCLIC MATCHING asks whether G has an acyclic mat...
详细信息
A matching Min 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 l is an element of N, ACYCLIC MATCHING asks whether G has an acyclic matching of size at least P. In this paper, we prove that assuming W[1] not subset of FPT, there does not exist any FPT-approximation algorithm for ACYCLIC MATCHING that approximates it within a constant factor when parameterized by P. Our reduction also asserts FPT-inapproximability for INDUCED MATCHING and UNIQUELY RESTRICTED MATCHING. We also consider three below-guarantee parameters for ACYCLIC MATCHING, viz. n/2 - P, MM(G) - P, and IS(G) - P, where n = V (G), MM(G) is the matching number, and IS(G) is the independence number of G. Also, 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 subset of coNP/poly. (c) 2024 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
暂无评论