0
$\begingroup$

Is it possible to reverse the result of the min-cut max-flow theorem and obtain the result that if you have the maximum cut, then you have the minimum flow? I've been thinking about it, but I have no clue if it's possible.

$\endgroup$
1
$\begingroup$

Yes. These are dual problems. Note that the max-flow problem can be formulated as a Linear Program. So the Max-Flow Min-Cut Theorem follows from LP duality.

$\endgroup$

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.