Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Applying a max-flow algorithm to the graph it's trivially possible to find one or two vertex covers, inverting source and sink and the directions of the flows. Is it possible to find more?

share|cite|improve this question

migrated from Dec 17 '12 at 21:39

This question came from our site for professional and enthusiast programmers.

In a graph with 2 vertexes and 1 edge between them, there exist 2 different vertex covers, correct? Or do you mean vertex cover size? But it's equal to number of edges in a maximum matching. – Victor Sergienko Dec 14 '12 at 0:10
You're right. I meant executing a max-flow algorithm without inverting source and sink (and edge directions). – Boanerghes Dec 14 '12 at 0:22
I must be not getting it. If you're looking for a cover from only one partition, then there exists only 1 cover for a partition - all the vertexes that have an incident edge, and 1 more cover in the other partition. But if you can combine the partitions, you will have more covers. – Victor Sergienko Dec 14 '12 at 0:35
That's the point: what do you mean by "combine partitions" (I guess you mean cuts)? Can you provide an example? I'm probably the one not getting it. It seems to me that even trying with different partitions, you always get the same vertex cover (or the same two, if you like). – Boanerghes Dec 14 '12 at 0:41
@VictorSergienko: I think you mean 4 different vertex covers [a,c], [a,d], [b,c], [b,d]. (E.g. your cover [a,b] covers the (a,b) edge twice and leaves the other edge uncovered.) – j_random_hacker Dec 14 '12 at 10:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.