p-Edge/vertex-connected vertex cover: Parameterized and approximation algorithms.

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]. [ABSTRACT FROM AUTHOR]