0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 1. What have you tried? We expect you to make a significant effort before asking, and to tell us what you've tried and what research you've done. 2. Please don't over-use bold. It is distracting. $\endgroup$ – D.W. Jan 9 '15 at 0:35
  • $\begingroup$ Is there anything more you know about the structure of your graph? Yes they are undirected, but anything else? Sometimes you get lucky by identifying some structure in your input, and then there might be a fast algorithm for listing or counting say (minimum) vertex covers for that class of graphs. $\endgroup$ – Juho Jan 9 '15 at 15:29
  • $\begingroup$ Juho, sorry, I only noticed your comment now. The graph is undirected and also connected. No other special attributes regarding its structure.. $\endgroup$ – Corneliu Zuzu Jan 9 '15 at 16:47
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ nice, concise answer, thank you very much! $\endgroup$ – Corneliu Zuzu Jan 10 '15 at 4:25
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ is that proven? please note that I am referring only to connected graphs. regarding the research I've done: this is for an application I'm creating, I'm not so good with algorithms so I currently use backtracking. I only searched Google for the answer, have given a bit of thought about a solution myself but I don't have much time to "waste" before I finish the application. cheers $\endgroup$ – Corneliu Zuzu Jan 9 '15 at 12:37
0
$\begingroup$

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.

http://eccc.hpi-web.de/report/2013/159/

$\endgroup$
  • 1
    $\begingroup$ if V = {1 2}, E = {(1 2)} and we add v0 = 3 the way you said to add it, we'll now have V = {1 2 3}, E = {(1 2) (1 3) (2 3)}. Picking only v0 = 3 does not result in a vertex cover (edge (1 2) is not "monitored"). Have I misunderstood your answer? $\endgroup$ – Corneliu Zuzu Jan 9 '15 at 12:46
  • $\begingroup$ Sorry! Thought of dominating set. $\endgroup$ – Spark Jan 9 '15 at 15:17
  • $\begingroup$ your edited answer implies that the posted problem is indeed NP-hard/NP-complete. If so, can you tell me where you found this information? $\endgroup$ – Corneliu Zuzu Jan 9 '15 at 15:54
  • $\begingroup$ You may want to check out this discussion: cstheory.stackexchange.com/questions/4880/… $\endgroup$ – Spark Jan 10 '15 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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