Reducing the Vertex Cover Number via Edge Contraction

International audienceThe Contraction(vc) problem takes as input a graph G on n vertices and two integers k and d, and asks whether one can contract at most k edges to reduce the size of a minimum vertex cover of G by at least d. Recently, Lima et al. [MFCS 2020, JCSS 2021] proved, among other results, that unlike most of the so-called blocker problems, Contraction(vc) admits an XP algorithm running in time f (d) • n O(d). They left open the question of whether this problem is FPT under this parameterization. In this article, we continue this line of research and prove the following results: 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. In particular, this answers the open question stated in Lima et al. [MFCS 2020] in the negative. It is NP-hard to decide whether an instance (G, k, d) of Contraction(vc) is a Yes-instance even when k = d, hence enhancing our understanding of the classical complexity of the problem. Contraction(vc) can be solved in time 2 O(d) • n k−d+O(1). This XP algorithm improves the one of Lima et al. [MFCS 2020], which uses Courcelle's theorem as a subroutine and hence, the f (d)-factor in the running time is non-explicit and probably very large. On the other hand, this shows that when k = d, the problem is FPT parameterized by d (or by k)