XSci

Improved NP-Hardness of Approximation for Max-3-Cut and for Max-k-Cut with Small k

Ziang Ni

Submitted by Ziang Ni

Published November 21, 2026 · Version v1, November 21, 2026 · DOI 10.66977/xsci.2611.003l

Theoretical Computer Science, Algorithms

Abstract

We prove that Max-3-Cut is NP-hard to approximate within a factor of 27/29+ε≈0.93127/29 + \varepsilon \approx 0.931. This improves the factor 16/17≈0.94116/17 \approx 0.941 of Austrin, O'Donnell, Tan and Wright, the best NP-hardness result for Max-3-Cut since 2012. (Their result, unlike ours, also holds for 3-colourable graphs.) We also improve the NP-hardness of Max-kk-Cut for every kk from 4 to 20; for instance, we obtain 45/47≈0.95745/47 \approx 0.957 for Max-4-Cut and 33/34≈0.97133/34 \approx 0.971 for Max-5-Cut, where the previous factors were 0.9870.987 and 120/121120/121.

Our reductions are gadget reductions from Håstad's linear equations over Z3\mathbb{Z}_3, with gadgets that have at most six auxiliary vertices. The main new idea is a negation trick: since the negation of an assignment is again an assignment, equations with right-hand sides tt and −t-t can be handled together, and this makes the resulting predicates symmetric under all permutations of the colours. We complement it with a general soundness criterion for such reductions: in effect, the best strategy of the adversary is to use a single colour pattern everywhere. This criterion is the strongest analysis that uses Håstad's theorem as a black box, and, using LP duality, we show that under it no gadget reduction from these equations can beat 27/2927/29 for Max-3-Cut.

Finally, we observe that a classical reduction from Max-3-Cut to Max-kk-Cut, applied more carefully, already gives 82/85≈0.96582/85 \approx 0.965 for Max-4-Cut on 4-colourable graphs, improving the previously stated 85/8685/86.

View PDF