← 研踪 PaperTrailarXiv:2604.10318 · v2
On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
首次提交 2026-04-12 02:53
版本更新 2026-11-09 06:52
雷达观测 2026-11-10 13:19
摘要
Max-Cut is a classical graph-partitioning problem where given a graph $G = (V,E)$, the objective is to find a cut $(S,S^c)$ which maximizes the number of edges crossing the cut. In a seminal work, Goemans and Williamson gave an $α_{GW} \approx 0.87856$-factor approximation algorithm for the problem, which was later shown to be tight by the work of Khot, Kindler, Mossel, and O'Donnell. Since then, there has been a steady progress in understanding the approximability at even finer levels, and a fundamental goal in this context is to understand how the structure of the underlying graph affects the approximability of the Max-Cut problem. In this work, we investigate this question by exploring how the chromatic structure of a graph affects the Max-Cut problem. While it is well-known that Max-Cut can be solved perfectly and near-perfectly in $2$-colorable and almost $2$-colorable graphs in polynomial time, here we explore its approximability under much weaker structural conditions such as when the graph is $3$-colorable or contains a large independent set. Our main contributions in this context are as follows: 1. We show Max-Cut is $α_{GW}$-hard to approximate for $3$-colorable graphs. 2. We identify a natural threshold $α^*$ such that the following holds. Firstly, for graphs which contain an independent set of size up to $α^*$, Max-Cut continues to be $α_{GW}$-factor hard to approximate. Furthermore, for any graph that contains an independent set of size $> α^*$, there exists an efficient $>α_{GW}$-approximation algorithm for Max-Cut. Our hardness results are derived using various analytical tools and novel variants of the Majority-Is-Stablest theorem, which might be of independent interest. Our algorithmic results are based on a novel SDP relaxation, which is then rounded and analyzed using interval arithmetic.
作者备注：Fixed a minor issue in Lemma 7.4 and other minor typos
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-09 06:52 · 最新观测版本
On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
Max-Cut is a classical graph-partitioning problem where given a graph $G = (V,E)$, the objective is to find a cut $(S,S^c)$ which maximizes the number of edges crossing the cut. In a seminal work, Goemans and Williamson gave an $α_{GW} \approx 0.87856$-factor approximation algorithm for the problem, which was later shown to be tight by the work of Khot, Kindler, Mossel, and O'Donnell. Since then, there has been a steady progress in understanding the approximability at even finer levels, and a fundamental goal in this context is to understand how the structure of the underlying graph affects the approximability of the Max-Cut problem. In this work, we investigate this question by exploring how the chromatic structure of a graph affects the Max-Cut problem. While it is well-known that Max-Cut can be solved perfectly and near-perfectly in $2$-colorable and almost $2$-colorable graphs in polynomial time, here we explore its approximability under much weaker structural conditions such as when the graph is $3$-colorable or contains a large independent set. Our main contributions in this context are as follows: 1. We show Max-Cut is $α_{GW}$-hard to approximate for $3$-colorable graphs. 2. We identify a natural threshold $α^*$ such that the following holds. Firstly, for graphs which contain an independent set of size up to $α^*$, Max-Cut continues to be $α_{GW}$-factor hard to approximate. Furthermore, for any graph that contains an independent set of size $> α^*$, there exists an efficient $>α_{GW}$-approximation algorithm for Max-Cut. Our hardness results are derived using various analytical tools and novel variants of the Majority-Is-Stablest theorem, which might be of independent interest. Our algorithmic results are based on a novel SDP relaxation, which is then rounded and analyzed using interval arithmetic.
查看此版本解读 →查看此版本原文 ↗