Max Cut

Input

Graph $G = (V, E)$, weight $w(e) \in \mathbb{Z}^{+}$ for each $e \in E$, positive integer $K$.

Question

Is there a partition of $V$ into disjoint sets $V_1$ and $V_2$ such that the sum of the weights of the edges from $E$ that have one endpoint in $V_1$ and one endpoint in $V_2$ is at least $K$?

Classes

• NP-complete

Comments

Remains NP-complete if $w(e) = 1$ for all $e \in E$ (the [problem:simple-max-cut] problem) (Garey et al., 1976), and if, in addition, no vertex has degree exceeding 3 (Yannakakis, 1978). Can be solved in polynomial time if $G$ is planar (Hadlock, 1975), (Orlova & Dorfman, 1972).

Proofs

NP-complete

Transformation from Maximum 2-Satisfiability (Karp, 1972).

Reducible from

• Maximum 2-Satisfiability

References

• Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3), 237–267. https://doi.org/10.1016/0304-3975(76)90059-1
• Yannakakis, M. (1978). Node-and edge-deletion NP-complete problems. Proceedings of the Tenth Annual ACM Symposium on Theory of Computing - STOC ’78. https://doi.org/10.1145/800133.804355
• Hadlock, F. (1975). Finding a Maximum Cut of a Planar Graph in Polynomial Time. SIAM Journal on Computing, 4(3), 221–225. https://doi.org/10.1137/0204019
• Orlova, G., & Dorfman, Y. (1972). Finding the Maximum Cut in a Graph. Engineering Cybernetics, 10, 502–506. https://ci.nii.ac.jp/naid/10022525097/en/
• Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations (pp. 85–103). Springer US. https://doi.org/10.1007/978-1-4684-2001-2_9