On the approximability of the vertex cover and related problems
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
In this paper we show that the problem of identifying an edge $(i,j)$ in a graph $G$ such that there exists an optimal vertex cover $S$ of $G$ containing exactly one of the nodes $i$ and $j$ is NP-hard. Such an edge is called a weak edge. We then develop a polynomial time approximation algorithm for the vertex cover problem with performance guarantee $2-\frac{1}{1+σ}$, where $σ$ is an upper bound on a measure related to a weak edge of a graph. Further, we discuss a new relaxation of the vertex cover problem which is used in our approximation algorithm to obtain smaller values of $σ$. We also obtain linear programming representations of the vertex cover problem for special graphs. Our results provide new insights into the approximability of the vertex cover problem - a long standing open problem.