← 研踪 PaperTrailarXiv:2611.01402 · v1
Improved NP-Hardness of Approximation for Max-3-Cut and for Max-k-Cut with Small k
首次提交 2026-11-01 09:14
版本更新 2026-11-01 09:14
雷达观测 2026-11-04 23:43
摘要
We prove that Max-3-Cut is NP-hard to approximate within a factor of $27/29+\varepsilon \approx 0.931$. This improves the factor $16/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-$k$-Cut for every $k$ from 4 to 20; for instance, we obtain $45/47 \approx 0.957$ for Max-4-Cut and $33/34 \approx 0.971$ for Max-5-Cut, where the previous factors were 0.987 and 120/121. Our reductions are gadget reductions from Håstad's linear equations over $\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 $t$ and $-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/29$ for Max-3-Cut. Finally, we observe that a classical reduction from Max-3-Cut to Max-$k$-Cut, applied more carefully, already gives $82/85 \approx 0.965$ for Max-4-Cut on 4-colourable graphs, improving the previously stated $85/86$.
作者备注：20 pages, 5 figures. Code, gadget families and certificates: https://github.com/ziangni-sys/max-3-cut
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-01 09:14 · 最新观测版本
Improved NP-Hardness of Approximation for Max-3-Cut and for Max-k-Cut with Small k
We prove that Max-3-Cut is NP-hard to approximate within a factor of $27/29+\varepsilon \approx 0.931$. This improves the factor $16/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-$k$-Cut for every $k$ from 4 to 20; for instance, we obtain $45/47 \approx 0.957$ for Max-4-Cut and $33/34 \approx 0.971$ for Max-5-Cut, where the previous factors were 0.987 and 120/121. Our reductions are gadget reductions from Håstad's linear equations over $\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 $t$ and $-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/29$ for Max-3-Cut. Finally, we observe that a classical reduction from Max-3-Cut to Max-$k$-Cut, applied more carefully, already gives $82/85 \approx 0.965$ for Max-4-Cut on 4-colourable graphs, improving the previously stated $85/86$.
查看此版本解读 →查看此版本原文 ↗