论文标题
P边/顶点连接的顶点盖：参数化和近似算法
p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms
论文作者
论文摘要
我们介绍并研究了连接的Vertexcover（VC）问题的两个自然概括：$ p $ - 边缘连接和$ p $ - vertex相连的VC问题（其中$ p \ geq 2 $是固定整数）。像连接的VC一样，两个新的VC问题都是FPT，但是除非$ np \ subseteq conp/poly $，否则不承认多项式内核，这是极不可能的。但是，我们证明这两个问题都承认时间有效的多项式尺寸近似内核化方案。我们获得了$ O（2^{o（pk）} n^{o（1）}）$ - $ p $ - 边缘连接的VC和$ o（2^{o（k^2）n^{o（1））$ - $ o（2^{o（k^2）} n^{o（1））$ - $ p $ - p $ -p $ - vertex-connnected vc vc。最后，我们描述了$ 2（p+1）$ - $ p $ - 边缘连接VC的近似算法。与连接的VC相比，新的VC问题的证明需要更多的复杂论证。特别是，对于近似算法，我们使用gomory-hu树和近似内核的结果，其结果跨越了$ p $ - vertex/edge-vertex/edge-ednect-inconted子图，$ p $ vertex/edgetex/edge-edge-connected图形由Nishizeki和Poljak（1994）以及Nagamochi和Nagamochi和1992（1992）独立地获得。
We introduce and study two natural generalizations of the Connected VertexCover (VC) problem: the $p$-Edge-Connected and $p$-Vertex-Connected VC problem (where $p \geq 2$ is a fixed integer). Like Connected VC, both new VC problems are FPT, but do not admit a polynomial kernel unless $NP \subseteq coNP/poly$, which is highly unlikely. We prove however that both problems admit time efficient polynomial sized approximate kernelization schemes. We obtain an $O(2^{O(pk)}n^{O(1)})$-time algorithm for the $p$-Edge-Connected VC and an $O(2^{O(k^2)}n^{O(1)})$-time algorithm for the $p$-Vertex-Connected VC. 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 subgraph of a $p$-vertex/edge-connected graph obtained independently by Nishizeki and Poljak (1994) and Nagamochi and Ibaraki (1992).
