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?

  • $\begingroup$ 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. $\endgroup$ – Victor Sergienko Dec 14 '12 at 0:10
  • $\begingroup$ You're right. I meant executing a max-flow algorithm without inverting source and sink (and edge directions). $\endgroup$ – Boanerghes Dec 14 '12 at 0:22
  • $\begingroup$ 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. $\endgroup$ – Victor Sergienko Dec 14 '12 at 0:35
  • $\begingroup$ 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). $\endgroup$ – Boanerghes Dec 14 '12 at 0:41
  • 1
    $\begingroup$ @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.) $\endgroup$ – j_random_hacker Dec 14 '12 at 10:06

Your Answer

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

Browse other questions tagged or ask your own question.