Affordable Access

Publisher Website

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

Authors
Journal
Journal of Discrete Algorithms
1570-8667
Publisher
Elsevier
Publication Date
Volume
8
Issue
1
Identifiers
DOI: 10.1016/j.jda.2009.01.005
Keywords
  • Connected Vertex Cover
  • Chordal Graphs
  • Bipartite Graphs
  • Planar Graphs
  • Hypergraphs
  • Approximation Algorithm

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.