Search

Given a graph G on n vertices and two integers k and d , the Contraction(vc) problem asks whether one can contract at most k edges to reduce the vertex cover number of G by at least d. Recently, Lima et al. [JCSS 2021] proved that Contraction(vc) admits an XP algorithm running in time f (d) ⋅ n O (d). They asked whether this problem is FPT under this parameterization. In this article, we prove that: (i) Contraction(vc) is W [1]- hard parameterized by k + d. Moreover, unless the ETH fails, the problem does not admit an algorithm running in time f (k + d) ⋅ n o (k + d) for any function f. This answers negatively the open question stated in Lima et al. [JCSS 2021]. (ii) Contraction(vc) is NP - hard even when k = d. (iii) Contraction(vc) can be solved in time 2 O (d) ⋅ n k − d + O (1). This improves the algorithm of Lima et al. [JCSS 2021], and shows that when k = d , Contraction(vc) is FPT parameterized by d (or by k). [ABSTRACT FROM AUTHOR]