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
0 comments:
Post a Comment
Let us know your responses and feedback