1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Apr 26, 2017 at 1:11
  • $\begingroup$ 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. $\endgroup$
    – Gavin Klondike
    Commented Apr 26, 2017 at 1:38
  • 4
    $\begingroup$ 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. $\endgroup$
    – David Richerby
    Commented Apr 26, 2017 at 7:03
  • 3
    $\begingroup$ 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. $\endgroup$
    – Juho
    Commented Apr 26, 2017 at 9:14

1 Answer 1

Reset to default
2
$\begingroup$

I had initially missed parts 2.3 and 3.

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.)

The hexagon's vertices all have degree two, so "highest edge count (total)" ​ won't do anything, and your algorithm will fall back on 2.2 for each loop through 2. Your algorithm's initial choice for the hexagon doesn't matter, and its next choice will be an arbitrary one of the three vertices in the hexagon's opposite half. If your algorithm chooses the middle of those three ​ (i.e., the opposite vertex), then its next choice won't matter and part 2 will finish by choosing an arbitrary one of the vertices in the remaining unmarked edge. If its last choice is the one that is opposite from its next-to-last choice, then S will be the four vertices vertices from two opposite edges, which is a minimal vertex cover, in which case part 3 can't remove anything.

$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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I don't know how to add pictures to here, but the algorithm seems to solve that problem too. In the case of the triangle and the disconnected edge (please excuse my math but I assume it looks like this A connects to B, B connects to C, C connects to A for the triangle; then D connects to E for the edge). In step 2 it ignores vertices with no unmarked edges which would only select 2 vertices in the triangle. If it did (somehow) select a third vertex in the triangle, step 3 would remove the redundant vertex. Is this what you're referring to? $\endgroup$
    – Gavin Klondike
    Commented Apr 26, 2017 at 2:20
  • $\begingroup$ That was what I was referring to. ​ I hope my answer now gives something your algorithm can fail on. $\hspace{.15 in}$ $\endgroup$
    – user12859
    Commented Apr 26, 2017 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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