Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430630 | Journal of Discrete Algorithms | 2010 | 14 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Bruno Escoffier, Laurent Gourvès, Jérôme Monnot,