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
- Sort the vertices by the number of edges associated; greatest to smallest O(nlogn)
- While there are unmarked edges in E: O(V)
- Select the vertices with the highest edge count (total), put vertex in set S, and mark it’s associated edges O(V*E)
- Break ties by prioritizing the vertices with the fewest marked edges. If a tie still exists, handle arbitrarily.
- Skip vertices that have no unmarked edges.
- For each vertex in S, in the order they were added:
- 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)
- Return S
Algorithm runs in O(V*E). The edge markings can be maintained in a VxV table.