Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs

Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme

Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007), Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs. https://basepub.dauphine.fr/handle/123456789/20728

View/Open

cahierLamsade262.pdf (476.9Kb)

Type

Document de travail / Working paper

Date

2007

Series title

Cahiers du Lamsade

Series number

262

Metadata

Show full item record

Author(s)

Escoffier, Bruno
Gourvès, Laurent
Monnot, Jérôme

Abstract (EN)

We study a variation of the vertex cover problem where it is required that the graph induced by the vertex cover is connected. We prove that this problem is polynomial in chordal graphs, has a PTAS in planar graphs, is APX-hard in bipartite graphs and is 5/3-approximable in any class of graphs where the vertex cover problem is polynomial (in particular in bipartite graphs). Finally, dealing with hypergraphs, we study the complexity and the approximability of two natural generalizations.

Subjects / Keywords

connected vertex cover; chordal graphs; bipartite graphs; planar graphs; hypergraphs; APX-complete; approximation algorithm