2020/09/17 by Carl Einarson, Gregory Gutin, Einarson, Carl +7
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2009.08158
openalex publication_date 2020/09/17 · openalex created_date 2022/08/27 · openalex updated_date 2026/07/28
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 ≥ 2 is a fixed integer). Like Connected VC, both new VC problems are FPT, but do not admit 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. We obtain an O(2O(pk)nO(1))-time algorithm for the p-Edge-Connected VC and an O(2O(k2)nO(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).