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?

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top