Reducing the vertex cover number via edge contractions

Abstract

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 . 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 . Moreover, unless the ETH fails, the problem does not admit an algorithm running in time 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 . (iii) Contraction(vc) can be solved in time . This improves the algorithm of Lima et al. [JCSS 2021], and shows that when , Contraction(vc) is FPT parameterized by d (or by k).