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

Carl Einarson, Gregory Z. Gutin (Corresponding author), Bart M. P. Jansen, Diptapriyo Majumdar, Magnus Wahlström

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

2 Citaten (Scopus)
99 Downloads (Pure)

Samenvatting

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(pk)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].

Originele taal-2Engels
Pagina's (van-tot)23-40
Aantal pagina's18
TijdschriftJournal of Computer and System Sciences
Volume133
DOI's
StatusGepubliceerd - mei 2023

Financiering

We are grateful to the reviewers for numerous useful suggestions, which led to a significant improvement over our initial presentation.

Vingerafdruk

Duik in de onderzoeksthema's van 'p-Edge/vertex-connected vertex cover: Parameterized and approximation algorithms'. Samen vormen ze een unieke vingerafdruk.

Citeer dit