arXiv · Oct 19, 2026
Optimal Algorithms and Hardness for Max-Cut in Bounded Degree Graphs
By Rares-Darius Buhai, Suprovat Ghoshal, Neng Huang et al.
We give a polynomial-time algorithm that achieves an α_GW + Ω(1/d)-approximation for Max 2-LIN(2) in weighted instances where each vertex appears in at most d constraints. This improves on the α_GW+Ω(1/d²)-approximation guarantee of [Hsieh-Kothari, ICALP'23]. We also show a matching Unique Games hardness under randomized polynomial-time reductions, thereby proving that the gain on α_GW is optimal up to polylog(d) factors. Here, α_GW ≈ 0.878 is the approximation ratio of the Goemans-Williamson algorithm. Our results resolve an open question due to Raghavendra and refute his conjectured optimal approximation ratio of α_GW + Ω(1/√d). Our local improvement scheme can be thought of as using an adaptive (based on the neighbors) shift applied to the Gaussian before using the GW sign rounding. This allows us to implement a “soft but simultaneous'' flipping decision at each vertex as opposed to hard but sequential flipping decisions in prior works. Our hardness results are based on a new sparsification lemma for graphs produced by the reduction from Unique Games [Khot-Kindler-Mossel-O'Donnell, SICOMP'07] that preserves the optimal values up to a factor of 1 ± ε while subsampling to an average degree of only O(1/ε). This is the first example of a CSP in which the optimal advantage on degree-d instances is asymptotically smaller than O(1/√d) [Trevisan, STOC'01]. A key idea in the proof of our sparsification theorem establishes new bounds on the number of “nearly optimal'' cuts in the output of the KKMO reduction. This step, in turn, relies on a new, robust inverse Majority-Is-Stablest theorem.