2022/02/07 by Lima, Paloma T., Santos, Vinicius F. dos, Sau, Ignasi +2
#05C15 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2202.03322
The 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. [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) ⋅ nO(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: 1. 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) ⋅ no(k + d) for any function f. In particular, this answers the open question stated in Lima et al. [JCSS 2021] in the negative. 2. 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. 3. CONTRACTION(vc) can be solved in time 2O(d) ⋅ nk - d + O(1). This XP algorithm improves the one of Lima et al. [JCSS 2021], 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 hard, it shows that when k=d, the problem is FPT parameterized by d (or by k).