Having found one minimum vertex cover of a connected undirected graph, is there a known polynomial-time algorithm for finding all the other minimum vertex covers of the graph, or is this problem NP-complete as well?
Another question: what other ways (not necessarily polynomial-time) of finding the other MVCs when having one of them are there, Other than backtracking or re-running the algorithm that found the first MVC? A good answer to my original question would suffice marking it as such.
Asked By : Corneliu Zuzu
Answered By : Pål GD
Just complementing on D.W.'s already correct answer.
Take a collection of disjoint copies of triangles. This has $2^{n/3}$ many vertex covers. If you add a universal vertex (a vertex connected to every other vertex), the graph obviously becomes connected.
Now, this universal vertex is always going to be in any minimum vertex cover. However, for the rest of the graph (the original triangles), you still need to cover all the edges. There are of course $2^{n/3}$ ways of choosing vertices to the vertex cover.
However, there is a well-known algorithm which enumerates every minimal vertex cover with polynomial delay, meaning that it takes polynomial time between every output. This means that in graphs with few vertex covers, you can do this relatively quickly.
For your second question, the simplest is probably the $2^k n^2$ algorithm where $k$ is the size of the optimal vertex cover. You branch on edges, deleting the vertex you chose to the vertex cover, and when you have an edgeless graph, you output the set of vertices you deleted.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/37087
0 comments:
Post a Comment
Let us know your responses and feedback