arxiv: 2604.10318 · v1 · submitted 2026-04-11 · 💻 cs.DS

Recognition: unknown

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets

Suprovat Ghoshal , Neng Huang , Euiwoong Lee , Konstantin Makarychev , Yury Makarychev

Authors on Pith no claims yet

Pith reviewed 2026-05-10 15:18 UTC · model grok-4.3

classification 💻 cs.DS

keywords max-cutapproximability3-colorable graphsindependent setsinapproximabilitySDPmajority-is-stablest

0 comments

The pith

Max-Cut remains α_GW-hard to approximate on 3-colorable graphs, with a threshold α* on independent set size separating hard cases from easier ones.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the Goemans-Williamson approximation ratio for Max-Cut is tight even when the input graph is 3-colorable. It further identifies a critical threshold α* for the size of the largest independent set: graphs with independence number at most α* inherit the same inapproximability, while those with larger independent sets admit efficient algorithms with strictly better approximation guarantees. These results clarify how weaker structural properties than bipartiteness still constrain or enable better Max-Cut approximations. The hardness proofs rely on new analytic variants of the Majority-Is-Stablest theorem, and the algorithm uses a custom SDP relaxation analyzed with interval arithmetic.

Core claim

We prove that it is NP-hard to approximate Max-Cut to within a factor better than α_GW ≈ 0.878 on 3-colorable graphs. We define a natural threshold α* such that Max-Cut is α_GW-hard on any graph whose largest independent set has size at most α*, but there is a polynomial-time algorithm achieving an approximation ratio strictly larger than α_GW whenever the independence number exceeds α*.

What carries the argument

The threshold α* on the relative size of the largest independent set, combined with novel variants of the Majority-Is-Stablest theorem used in the hardness reductions and a new SDP relaxation that is rounded and analyzed using interval arithmetic to obtain the improved approximation.

If this is right

Approximating Max-Cut better than α_GW is NP-hard on all 3-colorable graphs.
Graphs whose independence number is at most α* are hard to approximate for Max-Cut beyond α_GW.
Graphs with independence number larger than α* have a polynomial-time algorithm for Max-Cut with approximation factor exceeding α_GW.
The Majority-Is-Stablest theorem admits variants that establish hardness for structured graph classes.
The SDP relaxation with interval-arithmetic analysis provides approximation guarantees tailored to graphs with large independent sets.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

This implies that 3-colorability alone does not make Max-Cut easier to approximate than on arbitrary graphs.
Similar thresholds might exist for the approximability of other constraint satisfaction problems on graphs with large independent sets.
The use of interval arithmetic for analyzing SDP roundings could extend to other approximation algorithms under structural assumptions.
These results highlight a transition point where graph structure begins to help algorithmic performance beyond the general case.

Load-bearing premise

The novel variants of the Majority-Is-Stablest theorem developed here correctly establish the inapproximability results for 3-colorable graphs and for graphs with independent sets no larger than α*, and the SDP relaxation admits a rounding procedure that achieves an approximation factor strictly larger than α_GW.

What would settle it

Discovery of a polynomial-time algorithm that approximates Max-Cut better than α_GW on some family of 3-colorable graphs, or a counterexample showing that one of the new Majority-Is-Stablest variants does not hold.

Figures

Figures reproduced from arXiv: 2604.10318 by Euiwoong Lee, Konstantin Makarychev, Neng Huang, Suprovat Ghoshal, Yury Makarychev.

**Figure 1.** Figure 1: Sampling a ρ ∗ -Correlated Pair In other words, a random draw of an edge from HR ρ ∗ corresponds to sampling a pair of ρ ∗ -correlated strings from {0, 1} R. The completeness of the gadget can be established easily; consider the dictator cut S = {x ∈ {0, 1} R : x(1) = 1}. It can be easily seen that: Pr (x,y)∼HR ρ ∗ h S cuts (x, y) i = Pr (x,y)∼HR ρ ∗ h x(1) ̸= y(1) i = 1 − ρ ∗ 2 = c ∗ , i.e., the set S cut… view at source ↗

**Figure 2.** Figure 2: The Distribution µα Let I R α be the weighted graph on {0, 1} R, where edges in {0, 1} R × {0, 1} R are distributed as the R-fold product measure µ R α . Due to the definition of distribution µα, the graph I R α will satisfy the following properties: • The set I := {x ∈ {0, 1} R : x(1) = 1} is an independent set in I R α . • Exactly α-fraction of edges are incident on I in I R α . Furthermore, the spectral… view at source ↗

**Figure 3.** Figure 3: Reduction for Theorem 1.1 Parameters of the Reduction. We assign the following values to the parameters. 18 [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗

**Figure 4.** Figure 4: Reduction for Theorem 1.3 Parameters of the Reduction. We use assign the following values to the parameters. • Let α ∈ h 2ρ ∗ ρ ∗−1 , 0i . • Let η be as in Theorem 1.3. • Let τ be such that c(τ), c1(τ) ≤ η/10, where c(τ), c1(τ) are as in Theorem 3.4 and Lemma 3.5. • We set ε = η/4 and δ = τ 2η 2/8. We now state the completeness and soundness guarantees of the above reduction. Lemma 7.3 (Completeness) Suppo… view at source ↗

**Figure 5.** Figure 5: The semi-definite relaxation SDP(G) The relaxation can only increase the objective value, so we can find in polynomial time a set of vectors {vi | i ∈ {0} ∪ V} satisfying the SDP constraints such that 1 |E| ∑{i,j}∈E 1−vi ·vj 2 ≥ α. We will give a rounding algorithm that obtains a large cut given such an SDP solution. For every i, j ∈ V, let us define bi = vi · v0 and bij = vi · vj . It follows from the SDP… view at source ↗

**Figure 6.** Figure 6: Plot of the threshold function t as a function of the bias b. Plots in this paper are made with Matplotlib [Hun07]. The verification of this scheme can be summarized in the following lemma. Lemma 8.8 (Interval Arithmetic) 16 Let η = 10−13 and b0 ∈ [b ∗ − η, b ∗ + η]. Let t be defined as in [PITH_FULL_IMAGE:figures/full_fig_p042_6.png] view at source ↗

**Figure 7.** Figure 7: Contour plot of the function s(bi , bj) − p · bi+bj 2 + q . Red region is infeasible. Remark 8.9 The verification code for the above lemma is based on the Arb library [Joh17], which is part of the FLINT C libraries [The25]. We made use of a C++ wrapper for a fragment of Arb library which was recently made for verifying approximation ratios for MAX 2-CSP [BHPZ23, BHZ24]. We note that since in our verifi… view at source ↗

**Figure 8.** Figure 8: Gadget with Known Independent Set We begin by stating the completeness properties of the gadget that are straightforward to verify. Lemma 9.1 (Completeness) The graph H defined in [PITH_FULL_IMAGE:figures/full_fig_p044_8.png] view at source ↗

read the original abstract

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 $\alpha_{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 $\alpha_{GW}$-hard to approximate for $3$-colorable graphs. 2. We identify a natural threshold $\alpha^*$ such that the following holds. Firstly, for graphs which contain an independent set of size up to $\alpha^*$, Max-Cut continues to be $\alpha_{GW}$-factor hard to approximate. Furthermore, for any graph that contains an independent set of size $> \alpha^*$, there exists an efficient $>\alpha_{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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper shows that 3-colorability does not help Max-Cut approximation beyond the Goemans-Williamson threshold, while sufficiently large independent sets do allow a better guarantee via a new SDP rounding.

read the letter

The main thing to know is that this work shows Max-Cut stays hard to approximate better than α_GW even when the graph is 3-colorable, and it pins down a threshold α* on the size of the largest independent set where the hardness stops and a better algorithm kicks in. They do a good job separating the cases. The hardness part uses reductions based on new variants of the Majority-Is-Stablest theorem to show that the KKMO gap carries over to 3-colorable graphs and to graphs with small independent sets. On the positive side, they give an SDP-based algorithm that beats α_GW when the independent set is larger than α*, with the analysis done via interval arithmetic to get explicit bounds. The paper is careful about what is new. The α* threshold and the 3-colorable hardness aren't in the earlier literature they cite. The tools for hardness are presented as novel, which is fine as long as the proofs are there. The soft spot is that the entire hardness result depends on these new analytic tools being correct. Since they are variants, one has to verify the statements and the proofs carefully, but the abstract indicates they are developed inside the paper rather than assumed. The algorithmic analysis seems more standard once the SDP is set up, though interval arithmetic is a bit unusual but acceptable for rigor. No obvious issues with citations or self-referential fitting. The results are stated clearly with the threshold. This paper is aimed at approximation algorithms researchers interested in how structural properties affect cut problems. A reader working on Max-Cut or related CSPs would find the threshold result useful for understanding the boundary. It deserves a serious referee because the claims are specific, the techniques are non-routine, and if the new tools hold up it advances the understanding of the approximability landscape. I would recommend sending it out for peer review.

Referee Report

3 major / 3 minor

Summary. The manuscript claims that Max-Cut remains α_GW-hard to approximate on 3-colorable graphs and, more generally, on graphs whose maximum independent set has relative size at most a threshold α*. For graphs whose independence number exceeds α*, it presents a polynomial-time algorithm achieving an approximation factor strictly larger than α_GW. Hardness is obtained via reductions that invoke newly developed variants of the Majority-Is-Stablest theorem; the algorithmic side uses a custom SDP relaxation whose rounding is analyzed by interval arithmetic.

Significance. If the novel Majority-Is-Stablest variants and the interval-arithmetic rounding analysis hold, the results refine the structural understanding of Max-Cut approximability: 3-colorability alone does not improve upon the general-case threshold, while a precise transition occurs once the independence number surpasses α*. The algorithmic contribution supplies a concrete, rigorously verified improvement over α_GW for a natural graph class, and the analytic tools may be reusable. The work therefore sits at the intersection of hardness-of-approximation and SDP-based algorithms.

major comments (3)

[§4.2, Theorem 4.3] §4.2, Theorem 4.3 and the novel Majority-Is-Stablest variant (Eq. (4.5)): the stability bound is asserted to carry the α_GW gap from the KKMO construction while preserving 3-colorability. The reduction gadget must be shown not to increase the independence number or violate the coloring constraint; the current sketch does not explicitly compute the post-reduction independence number or verify that the chosen noise parameter ρ keeps the instance 3-colorable.
[§6, Definition of α*] §6, Definition of α* and Theorem 6.2: α* is defined as the solution to an optimization problem over noise stability. The manuscript must exhibit the numerical value of α* together with the interval-arithmetic certificate that the SDP rounding ratio exceeds α_GW exactly when the independence number surpasses this threshold; without the explicit margin and the verified interval bounds, the sharpness of the threshold cannot be assessed.
[§5, Eq. (5.3)] §5, SDP formulation (Eq. (5.3)) and rounding analysis: the custom SDP is claimed to be strictly tighter than the Goemans-Williamson SDP on graphs with large independent sets. The interval-arithmetic error bounds must be shown to guarantee a positive additive improvement over α_GW; the paper should supply either the full interval computations or a machine-checkable certificate confirming that the achieved ratio is at least α_GW + ε for a concrete ε > 0.

minor comments (3)

[Introduction] The numerical approximation α_GW ≈ 0.87856 is used throughout; the exact arccos-based definition should be recalled at least once for precision.
[§2] Notation for the independent-set threshold α* is introduced without a closed-form expression or an explicit optimization program; adding either would improve readability.
[Abstract] The abstract states that the Majority-Is-Stablest variants are “of independent interest”; a brief comparison table with the classical theorem would help readers gauge the technical novelty.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and will make the indicated revisions to strengthen the presentation and proofs.

read point-by-point responses

Referee: [§4.2, Theorem 4.3] §4.2, Theorem 4.3 and the novel Majority-Is-Stablest variant (Eq. (4.5)): the stability bound is asserted to carry the α_GW gap from the KKMO construction while preserving 3-colorability. The reduction gadget must be shown not to increase the independence number or violate the coloring constraint; the current sketch does not explicitly compute the post-reduction independence number or verify that the chosen noise parameter ρ keeps the instance 3-colorable.

Authors: We agree that the reduction sketch in §4.2 is insufficiently detailed on these points. In the revised manuscript we will add an explicit computation of the maximum independent-set size in the gadget (showing it remains bounded by α*) together with a direct verification that the chosen noise parameter ρ preserves 3-colorability of the constructed instance. These calculations will be inserted immediately after the statement of Theorem 4.3. revision: yes
Referee: [§6, Definition of α*] §6, Definition of α* and Theorem 6.2: α* is defined as the solution to an optimization problem over noise stability. The manuscript must exhibit the numerical value of α* together with the interval-arithmetic certificate that the SDP rounding ratio exceeds α_GW exactly when the independence number surpasses this threshold; without the explicit margin and the verified interval bounds, the sharpness of the threshold cannot be assessed.

Authors: We will include the numerical value of α* (obtained by solving the stated optimization problem) and the corresponding interval-arithmetic certificate in the revised §6. The certificate will explicitly bound the SDP rounding ratio and demonstrate that it exceeds α_GW by a positive margin precisely when the independence number surpasses α*, thereby confirming the sharpness of the threshold in Theorem 6.2. revision: yes
Referee: [§5, Eq. (5.3)] §5, SDP formulation (Eq. (5.3)) and rounding analysis: the custom SDP is claimed to be strictly tighter than the Goemans-Williamson SDP on graphs with large independent sets. The interval-arithmetic error bounds must be shown to guarantee a positive additive improvement over α_GW; the paper should supply either the full interval computations or a machine-checkable certificate confirming that the achieved ratio is at least α_GW + ε for a concrete ε > 0.

Authors: We acknowledge that the current rounding analysis in §5 does not display the explicit interval bounds or certificate. In the revision we will append the full interval-arithmetic computations (or a machine-checkable certificate) establishing that the achieved approximation ratio is at least α_GW + ε for a concrete ε > 0 whenever the independence number exceeds α*. This will rigorously confirm the strict improvement over the Goemans-Williamson factor. revision: yes

Circularity Check

0 steps flagged

No significant circularity; novel theorems and SDP form independent contributions

full rationale

The paper's hardness results for 3-colorable graphs and graphs with independent sets of size at most α* are obtained via reductions that invoke newly developed variants of the Majority-Is-Stablest theorem, which are proven inside the paper rather than presupposed or fitted to the target inapproximability gap. The α_GW-hardness base case is imported from the external Khot-Kindler-Mossel-O'Donnell construction. The algorithmic side introduces a fresh SDP relaxation whose rounding is analyzed via interval arithmetic to obtain a factor strictly larger than α_GW; no parameters are fitted to the final guarantee. No self-citations are load-bearing, no ansatz is smuggled, and no known result is merely renamed. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard mathematical background in Fourier analysis and semidefinite programming together with two newly introduced analytic statements (variants of Majority-Is-Stablest) whose validity is not independently verified outside the paper.

axioms (1)

standard math Standard facts from Fourier analysis on the hypercube and properties of semidefinite programming relaxations for Max-Cut
Invoked implicitly when applying Majority-Is-Stablest variants and when formulating the SDP relaxation

pith-pipeline@v0.9.0 · 5702 in / 1569 out tokens · 48334 ms · 2026-05-10T15:18:27.772157+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two
cs.DS 2026-04 unverdicted novelty 7.0

A new coordinatewise balanced covering theorem for linear gain graphs yields a randomized algorithm for Coset-List Min-2-Lin over powers of two with runtime exponential in k squared times the cycle-label rank rho.

Reference graph

Works this paper leans on

10 extracted references · 2 canonical work pages · cited by 1 Pith paper

[1]

Approximating max- imum cut on interval graphs and split graphs beyond goemans-williamson

[ADKL25] Jungho Ahn, Ian DeHaan, Eun Jung Kim, and Euiwoong Lee. Approximating max- imum cut on interval graphs and split graphs beyond goemans-williamson. InAp- proximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025), pages 20–1. Schloss Dagstuhl–Leibniz-Zentrum für Infor- matik,

2025
[2]

Finding colorings in one-sided expanders.arXiv preprint arXiv:2508.02825,

[BHSVK25] Rares-Darius Buhai, Yiding Hua, David Steurer, and Andor Vári-Kakas. Finding colorings in one-sided expanders.arXiv preprint arXiv:2508.02825,

work page arXiv
[3]

Approximation algorithms and hardness for strong unique games

48 [GL21] Suprovat Ghoshal and Anand Louis. Approximation algorithms and hardness for strong unique games. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 414–433. SIAM,

2021
[4]

Triangles improve 0.878 approxi- mation for maxcut

[GLP25] Fredie George, Anand Louis, and Rameesh Paul. Triangles improve 0.878 approxi- mation for maxcut. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025), pages 27–1. Schloss Dagstuhl– Leibniz-Zentrum für Informatik,

2025
[5]

d-to-1 hardness of coloring 3-colorable graphs with o (1) colors

[GS20] Venkatesan Guruswami and Sai Sandeep. d-to-1 hardness of coloring 3-colorable graphs with o (1) colors. In47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), pages 62–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik,

2020
[6]

Goemans and David P

[GW94] Michel X. Goemans and David P . Williamson. .879-approximation algorithms for MAX CUT and MAX 2sat. In Frank Thomson Leighton and Michael T. Goodrich, editors, Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 422–431. ACM,

1994
[7]

Approximating max-cut on bounded degree graphs: Tighter analysis of the fkl algorithm

[HK23] Jun Ting Hsieh and Pravesh K Kothari. Approximating max-cut on bounded degree graphs: Tighter analysis of the fkl algorithm. In50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, page

2023
[8]

Coloring 3-colorable graphs with low threshold rank.arXiv preprint arXiv:2508.03093,

[Hsi25] Jun-Ting Hsieh. Coloring 3-colorable graphs with low threshold rank.arXiv preprint arXiv:2508.03093,

work page arXiv
[9]

On the power of unique 2-prover 1-round games

[Kho02] Subhash Khot. On the power of unique 2-prover 1-round games. InProceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 767–775,

2002
[10]

Spectral algorithms for unique games

[Kol10] Alexandra Kolla. Spectral algorithms for unique games. InProceedings of the 25th An- nual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pages 122–130. IEEE Computer Society,

2010