Back to Search
Start Over
p-Edge/vertex-connected vertex cover: Parameterized and approximation algorithms.
- Source :
-
Journal of Computer & System Sciences . May2023, Vol. 133, p23-40. 18p. - Publication Year :
- 2023
-
Abstract
- 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]
- Subjects :
- *APPROXIMATION algorithms
*POLYNOMIAL time algorithms
*SUBGRAPHS
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 133
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 161158547
- Full Text :
- https://doi.org/10.1016/j.jcss.2022.11.002