Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 1 down vote favorite

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|improve this question
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
1  
@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
show 2 more comments

migrated from stackoverflow.com Dec 17 '12 at 21:39

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.