Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I'm trying to find a polynomial time algorithm for finding the minimum vertex cover for a graph. I've written the algorithm below; I know this problem is $\mathsf{NP}$-hard, which means there are probably some graphs for which this algorithm will not work.

I need some help in finding the flaw in this algorithm and also, an indication for what restrictions should be imposed on graphs such that this algorithm works.

In the algorithm below I have a graph $G=(V,E)$. I also define the $\text{priority}(v)$ function; in rough terms, it is the number of edges that are covered by vertex $v$. The function has the property that

$$\sum_{v \in V} \text{priority}(v) = \text{number of edges}.$$

In other words, an edge is counted as covered by only one of its vertices, not both.

Define degree : V -> NaturalNumbers
degree(v) = number of edges connected to v, for all v in V

Define priority : V -> NaturalNumbers
Initialize priority(v) = 0 for all v in V

For all (u, v) in E:
    If degree(u) >= degree(v):
        priority(u) = priority(u) + 1
    Else
        priority(v) = priority(v) + 1

Define S as the solution to the vertex cover problem
Initialize S to the empty set

For all v in V:
    If priority(v) != 0:
        Add v to the set S

Output S as the solution
share|improve this question
1  
You can find a counter-example here. –  user7376 Mar 23 '13 at 4:33

1 Answer 1

up vote 8 down vote accepted

Trying to take "high priority" i.e. high degree vertices over their neighbors will not work in all cases. This algorithm chooses $n-1$ for $C_n$ (Cycle Graph on $n$ vertices). It should choose either $(n-1)/2$ or $n/2$ if its odd or even. It also fails for Perfect Graphs.

I'm pretty sure this gives a $O(\log n)$ approximation too. If you order vertices by degree and greedily select vertices until all edges are covered, it is basically the same greedy algorithm as $O(\log n)$ set cover.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.