论文标题
通过边缘收缩减少顶点盖号
Reducing the Vertex Cover Number via Edge Contractions
论文作者
论文摘要
收缩（VC）问题将$ n $顶点上的图$ g $和两个整数$ k $和$ d $都作为输入，并询问是否可以最多收缩$ k $ edge，以减少至少$ d $的最低顶点封面的大小。最近，利马等人。 [JCSS 2021]证明，除其他结果外，与大多数所谓的阻止者问题不同，收缩（VC）接受了在时间$ f（d）\ cdot n^{o（d）} $中运行的XP算法。他们打开了这个问题是否在此参数化下fpt的问题。在本文中，我们将继续这一研究，并证明以下结果： 1。收缩（VC）是W [1] - 由$ K + D $参数化。此外，除非ETH失败，否则问题不接受任何功能$ f $的时间$ f（k + d）\ cdot n^{o（k + d）} $运行的算法。特别是，这回答了利马等人中提到的开放问题。 [JCSS 2021]在负面。 2。确定实例$（g，k，d）收缩（VC）是否是“是的”，即使$ k = d $，也可以增强我们对问题的经典复杂性的理解。 3。收缩（VC）可以在时间上解决$ 2^{o（d）} \ cdot n^{k -d + o（1）} $。该XP算法改善了Lima等人的一种。 [JCSS 2021]，它使用Courcelle的定理作为子例程，因此，运行时间中的$ f（d）$ - 因素不明显，可能很大。另一方面，它表明当$ k = d $时，问题是由$ d $（或$ k $）参数化的。
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) \cdot 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: 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) \cdot n^{o(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 $2^{O(d)} \cdot n^{k - 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$).
