Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
No, there is no polynomial-time algorithm: there can be exponentially many minimum vertex covers, so there is no way to list them all in polynomial time.
In general, there is little that we can say about ``promise'' variants of NP-hard problems. If I promise you that a solution to the problem exists, it is not clear that you'll be able to find it. There's another class of problems called PPAD, where you are guaranteed that a solution exists, but it is not known whether finding it can be done in polynomial time. Famous problems in PPAD include finding a fixed point of a function, and finding a Nash equilibrium in mixed strategies.
The following paper talks about such promise variants for SAT.
