# Having trouble proving vertex cover greedy algorithm

So this is my first time posting, but I don't know where else to go. I've spoken with several PHD and Masters students and they referred me here. I've been looking at the Vertex Cover problem and came up with an algorithm to find the optimal minimum. I've tried this on several graphs as examples and it's found the optimal every time. Could someone please help me prove that either this finds the optimal for all VC problems or if there is a counter example disproving it? Thanks in advance.

Given Graph G = (V,E), find minimum Vertex Cover

1. Sort the vertices by the number of edges associated; greatest to smallest O(nlogn)
2. While there are unmarked edges in E: O(V)
1. Select the vertices with the highest edge count (total), put vertex in set S, and mark it’s associated edges O(V*E)
2. Break ties by prioritizing the vertices with the fewest marked edges. If a tie still exists, handle arbitrarily.
3. Skip vertices that have no unmarked edges.
3. For each vertex in S, in the order they were added:
1. Remove vertex from set S and update edge markings. If any associated edge becomes unmarked, reselect vertex and remark the edges. Otherwise, remove vertex from S (nobody wanted them anyways 😝) O(V*E)
4. Return S

Algorithm runs in O(V*E). The edge markings can be maintained in a VxV table.

• Welcome to CS.SE! Have you tried to prove your algorithm correct? Have you tried running it on millions of randomly generated graphs, and comparing its output to a brute-force algorithm that is known to be correct, to search for counterexamples? Vertex Cover is NP-hard, so if your algorithm is correct, it would imply P=NP, which would amount to a major breakthrough. It isn't our purpose on this site to try to make major breakthroughs or review claims of major breakthroughs, such as a claim to have proven that P=NP. Personally, I doubt the algorithm is correct. – D.W. Apr 26 '17 at 1:11
• I also doubt the algorithm is correct, but I don't know how to prove that it is. NP-hard and NP-complete problems are so complex that, to my knowledge, there isn't a way. I like your idea of following up with randomly generated graphs but I can see two major problems: 1) if it works for those graphs, how do I prove that it works for all graphs or is better than the current approximation algorithm? 2) How would I know that testing against graphs is complete (RE: Decidable TMs). Thanks for your input, I'll keep looking into this. – Gavin Klondike Apr 26 '17 at 1:38
• I'm voting to close this question as off-topic because it is a request to verify what would amount to a major breakthrough in theoretical computer science. – David Richerby Apr 26 '17 at 7:03
• Looks like the algorithm is easy to implement. Do that and run it on small examples and compare with optimal solutions you get with say brute force. – Juho Apr 26 '17 at 9:14

If I'm not still missing something, then your algorithm can find a non-optimal cover for the hexagon, and necessarily finds a non-optimal cover for ​ $K_{3,3}$ minus one edge. (Those are both connected balanced-bipartite graphs, so each half of their bi-partitions is a three-vertex vertex cover.)
$K_{3,3}$ minus one edge has four vertices with degree three and no vertices with higher degree.Those four vertices are each adjacent to a degree-two vertex, so will all be put into S. Due to the removed edge, putting those four in will result in there being no unmarked edges. Since only that edge was removed, S is a minimal vertex cover, so part 3 can't remove anything from it.
• That was what I was referring to. ​ I hope my answer now gives something your algorithm can fail on. $\hspace{.15 in}$ – user12859 Apr 26 '17 at 6:29