p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms
p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms
复制标题
p 边/顶点连接的顶点覆盖：参数化和近似算法
DOI：
10.1016/j.jcss.2022.11.002
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Magnus Wahlström
中科院分区：
文献类型：
--
作者：
Carl Einarson;G. Gutin;B. Jansen;Diptapriyo Majumdar;Magnus Wahlström
引入并研究了连通顶点覆盖（VC）问题的两种自然推广：p边连通和p顶点连通VC问题（其中p≥2是一个固定整数）。得到了p边连通VC的一个2o (kp) n O(1)时间算法和p点连通VC的一个2o (k2) n O(1)时间算法。因此，与连通风险投资一样，约束风险投资问题都是FPT。此外，与Connected VC一样，除NP≥coNP/poly外，任何问题都不存在多项式核，这是极不可能的。然而，我们证明了这两个问题都具有时间效率的多项式大小的近似核化方案。最后，给出了p边连通VC的2 （p+ 1）逼近算法。新的VC问题的证明需要比Connected VC更复杂的论证。特别是，对于近似算法，我们使用Gomory-Hu树，对于近似核，Nishizeki和Poljak(1994)[30]和Nagamochi和Ibaraki(1992)[27]在p顶点/边连通图的小尺寸生成p顶点/边连通子图上得到的结果。
We introduce and study two natural generalizations of the Connected Vertex Cover (VC) problem: the p-Edge-Connected and p-Vertex-Connected VC problem (where p≥ 2 is a fixed integer). We obtain an 2 O (p k) n O (1)-time algorithm for p-Edge-Connected VC and an 2 O (k 2) n O (1)-time algorithm for p-Vertex-Connected VC. Thus, like Connected VC, both constrained VC problems are FPT. Furthermore, like Connected VC, neither problem admits a polynomial kernel unless NP⊆ coNP/poly, which is highly unlikely. We prove however that both problems admit time efficient polynomial sized approximate kernelization schemes. Finally, we describe a 2 (p+ 1)-approximation algorithm for the p-Edge-Connected VC. The proofs for the new VC problems require more sophisticated arguments than for Connected VC. In particular, for the approximation algorithm we use Gomory-Hu trees and for the approximate kernels a result on small-size spanning p-vertex/edge-connected subgraphs of a p-vertex/edge-connected graph by Nishizeki and Poljak (1994)[30] and Nagamochi and Ibaraki (1992)[27].