[Solved]: For what special cases does this vertex cover algorithm fail or work?

Problem Detail: 

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 

Asked By : Paul Manta

Answered By : Nicholas Mancuso

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7400