Improved NP-Hardness of Approximation for Max-3-Cut and for Max-k-Cut with Small k
Ziang Ni
Abstract
We prove that Max-3-Cut is NP-hard to approximate within a factor of . This improves the factor 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--Cut for every from 4 to 20; for instance, we obtain for Max-4-Cut and for Max-5-Cut, where the previous factors were and .
Our reductions are gadget reductions from Håstad's linear equations over , 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 and 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 for Max-3-Cut.
Finally, we observe that a classical reduction from Max-3-Cut to Max--Cut, applied more carefully, already gives for Max-4-Cut on 4-colourable graphs, improving the previously stated .