2
$\begingroup$

I'd like to ask a question about MAX CUT and MIN CUT on graphs with unit edge-weight. I know that MAX CUT is NP-Hard, but MIN CUT is in P (i think)?

Barahona, in 1982, showed (Lemma 1) finding a cut of at least k on a unit-weight graph is equivalent to finding a cut of at most -k on a graph in which each edge is replaced with a chain of edges, each of weight +1 except for one with weight -1. http://yaroslavvb.com/papers/barahona-on.pdf

Is this not technically MIN CUT on that extended graph? Wouldn't this show that MAX CUT can be reduced to MIN CUT, and therefore belong in P or is there something about MIN CUT I don't understand properly?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Both problems you mention have the stated complexity only when edge weights are non-negative. With these constraints, the reduction you describe no longer works.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.