On the approximability of the vertex cover and related problems

Details On the approximability of the vertex cover and related problems On the approximability of the vertex cover and related problems

2007-12-20

arxiv.org/abs/0712.3333v1

Computer Science

Data Structures and Algorithms

Scientific paper

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+\sigma}$, where $\sigma$ 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 $\sigma$. 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.

Affiliated with

Also associated with

No associations

Rating

On the approximability of the vertex cover and related problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the approximability of the vertex cover and related problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the approximability of the vertex cover and related problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-2601