1
$\begingroup$

I have simple undirected graph. I want to determine a size of minimum vertex cover, a size of maximal independent set and a size of a global minimum cut.

A minimum vertex cover is complementary to a maximum independent set. So, I can find one of this this and get both of them.

Is there any relation with global minimum cut? Or I have to find this size independent from other?

$\endgroup$
2
2
$\begingroup$

Minimum cut can be computed efficiently (you haven't explained what global minimum cut is, but presumably it reduces to minimum $s$-$t$ cut). Minimum vertex cover (probably) cannot. So any connection would be rather indirect. Minimum cut is related to another quantity, maximum flow, which is defined more generally for weighted directed graphs. Both quantities are equal due to the fundamental max-flow min-cut theorem (sometimes known as the min-cut max-flow theorem).

$\endgroup$
1
  • $\begingroup$ global minimum cut is calculated in O(n^3) without flow (you can find global minimum cut with max flow, but in O(n^4). $\endgroup$ – David May 7 '15 at 0:10

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.