For what special cases does this vertex cover algorithm fail or work?

Question

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

Answer 1

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.