On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets".
Jane: Here's the gist of the paper. Max-Cut is investigated in this work by exploring how graph structure, specifically 3-colorability and the presence of large independent sets, affects its approximability beyond the Goemans-Williamson factor In particular, the paper shows that Max-Cut remains hard to approximate beyond the standard αGW factor for 3-colorable graphs and graphs containing an independent set of a certain volume The main contributions include showing Max-Cut is αGW-hard to approximate for 3-colorable graphs and identifying a natural threshold α∗ related to the size of the independent set.
Tom: Hardness Results on Graph Structure The paper establishes hardness results based on the Unique Games Conjecture (UGC) using PCP-based gadget reductions Theorem 1.1 shows that Max-Cut is NP-hard to distinguish between cases where the graph is 3-colorable and cases where the cut size exceeds a certain threshold Theorem 1.2 extends this hardness to graphs containing an independent set with a specific relative volume, showing that Max-Cut is hard to approximate beyond αGW for such instances.
Jane: Theorem 1.3 further introduces a threshold α∗ and shows that if a graph contains an independent set with more than this fraction of edges incident on it, one can achieve better than the αGW-approximation.
Tom: Technical Gadget Construction The hardness reductions rely on constructing specific gadgets derived from noisy-cube and tripartite noisy-cube structures The construction for 3-colorable graphs involves a tripartite noisy-cube graph G Rρ (V, E) where each set Vi is an independent set, and the distribution on edges is defined by sampling pairs of indices (i, j) and correlated pairs of strings The construction for graphs with large independent sets involves a tensor product of the ρ∗-noisy cube HRρ and a gadget IRα that encodes an independent set I with an α-fraction of incident edges.
Title and authors: Jane: So what’s the actual mechanism they use to prove these hardness results? How are they connecting graph coloring and the cut size measurement?
Tom: They use specific gadgets constructed from noisy-cube structures, like a tripartite noisy-cube graph. For three-colorable graphs, they build this structure where each set has to be an independent set, and the way edges are distributed is controlled by sampling pairs of indices and correlated strings <ref:2604.10318#pg1>.
Lu: For the graphs with large independent sets, they use a tensor product of a specific noisy cube graph and another gadget that encodes an independent set with a certain fraction of incident edges. It’s this specific construction that allows them to prove the hardness.
Meng: From an engineer's viewpoint, constructing these gadgets sounds incredibly complicated to implement in practice for real-world graphs; how does that complexity translate into the actual approximation guarantee?
Tom: They tackle that with analysis using novel variants of the Majority-Is-Stablest theorem, specifically a tripartite version. Lemma five point three characterizes the optimal cut value for their Gaussian analogue based on whether some parameter rho is less than minus one over two or greater than or equal to minus one over two.
Jane: That’s where the noise stability comes in, and they use Fourier analysis and bounds like Theorem three point four to establish the necessary guarantees for those quasirandom sets within these gadgets.
Lu: It’s interesting because they are using these very advanced analytic tools—SDP relaxations followed by interval arithmetic rounding—to prove things about Max-Cut that were previously only proven under simpler assumptions.
Tom: The main point is showing that their SDP relaxation, when rounded with the T HRESH family of rounding schemes, gives an expected cut size greater than arccos rho star pi when that independent set condition is met.
The paper's summary: Jane: So if we take this whole setup—the hardness results and the analysis—what is the practical improvement they actually offer for someone trying to solve Max-Cut problems?
Tom: Theorem one point four presents a polynomial-time algorithm to find a cut that beats the Goemans Williamson approximation when an independent set I exists with more than alpha star fraction of incident edges. That’s a concrete result.
Lu: This algorithm works by solving a semi-definite program relaxation and then rounding the solution using that T HRESH family of rounding schemes they developed. It turns the theoretical hardness into a practical, albeit polynomial-time, solution for these structured instances.
Meng: So this means if you can measure or estimate how large an independent set is relative to its incident edges, you might be able to switch from expecting a poor approximation to getting one that’s guaranteed better than what we currently know.
Tom: Right. And they defined that threshold alpha star specifically related to the size of the independent set, which was their key contribution in identifying where the structural properties change the game.
Jane: They also suggested a connection between these hardness results and a framework called Valued PCSPs, implying that this setting is a natural example of where one evaluation method implies another.
Lu: Applying their analytic methods—the novel SDP relaxation and interval arithmetic analysis—to analyze valued PCSPs could open up new ways to determine if an instance has desirable solution properties across different evaluation methods.
The paper's improvements: Tom: So to wrap this up, the paper "On the Approximability of Max-Cut on three-Colorable Graphs and Graphs with Large Independent Sets" shows that graph structure matters beyond just basic coloring <ref:2604.10318#pg1,On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs>. It tells us exactly when we can expect a better than Goemans Williamson approximation.
Jane: They’ve identified that for three-colorable graphs and graphs with large independent sets, the standard approximation factor isn't always the best; there are specific structural conditions—defined by alpha star—where we get a guaranteed improvement via this new polynomial-time algorithm <ref:2604.10318#pg1,3-colorable graphs and graphs with large independent sets>.
Lu: The framework they developed for analyzing Valued PCSPs using SDP relaxation and interval arithmetic is really significant because it suggests a broader way to look at how different methods of finding solutions interact on these types of problems.
Meng: For deployment, the real question is how robust this works when we actually feed it messy, real-world data where estimating that independent set volume might be noisy. That’s the gap between theory and what breaks at scale.
Lalam: I'm confident in the results; based on my literature review, these structural constraints lead directly to these hardness results, and their polynomial-time algorithm is sound for those specific instances.
Tom: Exactly, Lalam. It’s a clear line: structure dictates performance limits and also opens up new paths for better solutions when we know the right conditions are met. That’s it for this one.
Conclusion: Jane: So, we’ve been talking about this paper on "On the Approximability of Max-Cut on three-Colorable Graphs and Graphs with Large Independent Sets." Basically, they found that for these specific graph structures—the ones that are three-colorable or have really big independent sets—you can't do much better than the standard Goemans Williamson approximation factor unless you hit a certain structural threshold.
Tom: Right. The core finding is that they’ve figured out exactly when the standard approximation stops being good, and when a specific algorithm actually kicks in to get you something better than that baseline.
Lu: They introduced this threshold alpha star, which depends on how big that independent set is relative to the edges it touches. If the volume of that independent set is bigger than this alpha star value, then a polynomial time algorithm gives you a cut size better than what we’d expect from just using the standard factor.
Meng: From an engineering standpoint, that means if you know your graph has a massive independent set following that specific rule, you can switch strategies immediately instead of wasting time trying to squeeze out more approximation on something that’s fundamentally limited.
Lalam: I’m confident in this because their construction of the noisy cube gadgets and the noise stability analysis provide a solid foundation for proving these hardness results. It connects the graph structure directly to the performance limits using very rigorous bounds.
Jane: It does sound like this is really about moving from a purely theoretical "it's hard" statement to a practical "here’s how you get a good solution."
Tom: Precisely. The paper shows that by looking at the density of these independent sets, we can predict whether we need to rely on the standard approximation or if we have enough structure for a better result.
Lu: And they also touched on how this framework applies to Valued PCSPs, suggesting their analytic tools might be useful in those areas too. It’s about seeing if the same math works across different ways of measuring things.
Meng: I'm still thinking about what it costs to run these kinds of checks on massive graphs in production, but having this structural predictor is definitely something an AI system could use to route its approximation strategy faster.
Lalam: The paper "On the Approximability of Max-Cut on three-Colorable Graphs and Graphs with Large Independent Sets" provides a very clear roadmap for understanding when Max-Cut problems are hard to approximate and when they aren't.
Jane: It’s a solid piece of work showing that the underlying structure of the graph isn't just background noise; it dictates the best possible performance we can achieve on Max-Cut problems.
Tom: Yeah, so if you’re working on a Max-Cut problem right now, checking for those independent set volumes might be your first move to see if you can jump from a standard approximation to something stronger.
Lu: We’ll be looking at how these structural constraints interact with other problems in the next few episodes. Stay tuned.
Suprovat Ghoshal, Neng Huang, Euiwoong Lee, Konstantin Makarychev, Yury Makarychev
Indiana University · University of Michigan · Northwestern University · Toyota Technological Institute at Chicago
cs.DS
Submitted: 2026-04-11
Updated: 2026-11-08
Comments: Fixed a minor issue in Lemma 7.4 and other minor typos
Code: https://github.com/nenghuang/max-cut-independent-set
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 76/100
The gist: Max-Cut is investigated in this work by exploring how graph structure, specifically 3-colorability and the presence of large independent sets…
Key concepts
- Max-Cut
- This problem seeks to partition the vertices of a graph into two sets such that the number of edges crossing between these sets is maximized. It's a fundamental problem in combinatorial optimization used to model various partitioning tasks.
- 3-Colorability
- A graph is 3-colorable if its vertices can be colored using only three distinct colors such that no two adjacent vertices share the same color. The paper studies how this structural property affects the difficulty of finding a good Max-Cut.
- Independent Set Volume
- This refers to the size or relative volume of an independent set within a graph. An independent set is a group of vertices where no two vertices are connected by an edge, and its 'volume' measures how large it is compared to other structural elements.
- Valued PCSPs
- Promise Constraint Satisfaction Problems (PCSPs) are problems where constraints have associated values. This framework allows the authors to connect Max-Cut hardness results to a broader class of problems where different evaluation methods might imply one another.
Terminology
Summary
Max-Cut is investigated in this work by exploring how graph structure, specifically 3-colorability and the presence of large independent sets, affects its approximability beyond the Goemans-Williamson factor In particular, the paper shows that Max-Cut remains hard to approximate beyond the standard αGW factor for 3-colorable graphs and graphs containing an independent set of a certain volume The main contributions include showing Max-Cut is αGW-hard to approximate for 3-colorable graphs and identifying a natural threshold α∗ related to the size of the independent set. p. 0 Specifically, we consider the settings where the graph is
3-colorable or contains a large independent set (in terms of its volume), and we ask if Max-Cut is
easier to approximate in such instances. Our main contributions in this context are as follows:
• We show Max-Cut is αGW-hard to approximate for 3-colorable graphs.Where the paper says it
Hardness Results on Graph Structure
The paper establishes hardness results based on the Unique Games Conjecture (UGC) using PCP-based gadget reductions Theorem 1.1 shows that Max-Cut is NP-hard to distinguish between cases where the graph is 3-colorable and cases where the cut size exceeds a certain threshold Theorem 1. p. 5 87856
denote the corresponding worst-case approximation ratio. In the hardness results stated below,
our YES and NO cases always distinguish between when the optimal max-cut is of size at least
c
∗
:=
1−ρ
∗
2 ≈ 0. Specifically, we consider the settings where the graph is
3-colorable or contains a large independent set (in terms of its volume), and we ask if Max-Cut is
easier to approximate in such instances. Our main contributions in this context are as follows:
• We show Max-Cut is αGW-hard to approximate for 3-colorable graphs. 4 for a discussion which explains the origins of this
threshold in more detail. We also give a sharp converse to the above theorem, in which we show
that if a graph indeed contains a independent set which has more than α
∗
-fraction of edges incident
on it, then we can achieve better than αGW-approximation for Max-Cut.Where the paper says it
Where the paper says it
Where the paper says it
Technical Gadget Construction
The hardness reductions rely on constructing specific gadgets derived from noisy-cube and tripartite noisy-cube structures The construction for 3-colorable graphs involves a tripartite noisy-cube graph G Rρ (V, E) where each set Vi is an independent set, and the distribution on edges is defined by sampling pairs of indices (i, j) and correlated pairs of strings The construction for graphs with large independent sets involves a tensor product of the ρ∗-noisy cube HRρ and a gadget IRα that encodes an independent set I with an α-fraction of incident edges.
Analysis via Noise Stability
The soundness analysis employs novel variants of the Majority-Is-Stablest theorem, specifically a tripartite variant, to bound the maximum cut value achievable by quasirandom sets in these gadgets Lemma 5.3 characterizes the optimal cut value for the Gaussian analogue of the tripartite gadget based on whether ρ is less than −1/2 or greater than or equal to −1/2. p. 9 For any quasirandom function f :
V1 ∪ V2 ∪ V3 → {0, 1}, we have
Pr
e∼GR
ρ
∗
h
f cuts ei
≤
arccos ρ
∗
π
+ o(1)
Moreover, the RHS is attained (up to o(1)-term) by f(i, x) := MAJ(x), where MAJ is the majority function. We point out that our actual lemma is more general, and completely characterizes the tripartite
noisy-cube gadget for all ρ ∈ (−1, 0]. 1 Fourier Analysis . 2 Gaussian Noise Stability . The completeness and soundness guarantees taken together imply that Max-Cut is hard to approximate beyond αGW = s
∗/c
∗ ≈ 0. 2 Max-Cut on 3-Colorable Graphs
Now, to establish Theorem 1.Where the paper says it
Where the paper says it
Where the paper says it
Approximation Algorithm for Large Independent Sets
Theorem 1.4 provides a polynomial-time algorithm to find a cut better than αGW approximation when an independent set I exists with more than α∗ fraction of incident edges This algorithm involves solving a semi-definite program relaxation and rounding the solution using the T HRESH− family of rounding schemes The soundness analysis for this algorithm relies on Lemma 8. p. 6 Now, the above theorem states
that the αGW-factor hardness also holds for instances which contain independent sets of relative
volume at most s
∗/2 ≈ 0. Furthermore, the above result is tight in the following sense: if
the independent set had more than s
∗
-fraction of edges incident on it, then since the independent
set I is known to the algorithm, it can trivially achieve better than αGW-approximation by simply
returning the cut (I, I
c
). 5 Overview of the Algorithm . 6 Proof Sketch of Lemma 2. 8445 and the case when the optimal max-cut is of size at most s
∗
:=
arccos ρ
∗
π ≈ 0. 742,
where c
∗ and s
∗ are the SDP value and the (expected) rounded value on an edge whose vectors
have inner-product ρ
∗
.Where the paper says it
Where the paper says it
Where the paper says it
Connection to Valued PCSPs
The paper suggests a connection between the results in Theorems 1.3 and 1.4 and the Valued PCSP framework, suggesting that the setting is a natural example of valued PCSPs where one evaluation method implies another The authors explore whether their analytic methods can be applied more broadly to valued PCSPs. p. 7 Our setting seems a natural example of valued PCSPs
since we may think of each edge as one (valued) Boolean constraint P, where in the independent
set case we have P(0, 0) = 0, P(1, 0) = P(0, 1) = 1, P(1, 1) = −∞ (where 1 means that the variable
is in the independent set, so the endpoints can’t both be 1), and in the MAX CUT case we have
P(0, 0) = (1, 1) = 0, P(1, 0) = P(0, 1) = 1. It would be interesting to explore whether our analytic
methods in this paper can be applied more broadly to valued PCSPs, or in the other direction,
whether the algebraic tools developed in [BBK+24] can shed more light on problems discussed in
this paper.Where the paper says it
Related Work and Context
The paper discusses related problems such as coloring graphs with small numbers of colors and finding large independent sets It references recent state-of-the-art results in these areas, including efficient algorithms for coloring 3-colorable graphs and progress on finding near-optimal colorings and independent sets in structured graphs. The work also touches upon the interplay between graph-cut problems and graph coloring using Promise CSPs. p. 7 There has also been recent progress on finding near-optimal colorings and independent
sets in the setting when the underlying graph is a one-sided expander [BHK25, BHSVK25], or has
low-threshold rank [Hsi25]. Another interesting related work is that of Nakajima and Živný [NŽ25],
which explores the interplay between graph-cut problems and graph coloring using the lens of
Promise CSPs; in particular, they show that given a Max-Cut instance G, one can efficiently find a
3-partition which cuts SdpVal(G) fraction of edges in G, where SdpVal(G) is the optimal value of
the standard SDP relaxation for Max-Cut on G.Where the paper says it
Auxiliary Proofs
Auxiliary proofs include detailed derivations for the noise stability bound, such as Lemma 7.6, which bounds the expected cut value in terms of correlation and noise parameters Furthermore, Appendix A. p. 5 8445 and the case when the optimal max-cut is of size at most s
∗
:=
arccos ρ
∗
π ≈ 0. 742,
where c
∗ and s
∗ are the SDP value and the (expected) rounded value on an edge whose vectors
have inner-product ρ
∗
. For any quasirandom function f :
V1 ∪ V2 ∪ V3 → {0, 1}, we have
Pr
e∼GR
ρ
∗
h
f cuts ei
≤
arccos ρ
∗
π
+ o(1)
Moreover, the RHS is attained (up to o(1)-term) by f(i, x) := MAJ(x), where MAJ is the majority function. We point out that our actual lemma is more general, and completely characterizes the tripartite
noisy-cube gadget for all ρ ∈ (−1, 0]. Moreover, the completeness of the gadget can be argued as before – we can define an analogous
dictator set S := ∪i∈[3]{(i, x) : x(1) = 1} – and using identical arguments as above, one can show
that this again cuts 1−ρ
∗
2
-fraction of the edges in G
R
ρ
∗ . Now, for the soundness guarantee, we would
again like to use Majority-Is-Stablest (Theorem 2. 3 Influence Decoding Lemma . 52
B Some Derivatives for Interval Arithmetic Verification 53
2 2 Gaussian Noise Stability . 3 Correlation and Noise Stability . Clearly, in G
R
ρ
∗ , each of the sets V1, V2, V3 is
an independent set, and hence the graph G
R
ρ
∗ is 3-colorable. Furthermore, when this gadget is
combined with UNIQUE GAMES problem as the outer-verifier, the final hard instance output by our
reduction will also inherit the 3-colorability of G
R
ρ
∗ . 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. – For any graph that contains an independent set of size > α
∗
, there exists an efficient
> αGW-approximation algorithm for Max-Cut. *Companion code: https://github. In this regard, a broad
ongoing effort revolves around understanding how the structure of the input graph affects the
approximability of Max-Cut. For instance, Max-Cut has been shown to admit improved approximation ratios for various classes structured instances, such as bounded-degree graphs [FKL02, HK23],
graphs with large spectral gap [AKK+08, Kol10, MM10] or low threshold rank [BRS11, GS11],
graphs with a linear number of edge-disjoint triangles [GLP25, ADKL25], dense graphs [AKK95],
interval graphs [ADKL25], and graphs with a low-rank SDP solution [AZ05].Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improve Max-Cut approximation for 3-colorable graphs by distinguishing between hard instances and those containing large independent sets based on a threshold alpha star = 2 rho star / rho star minus one. The improved system can determine if a graph is hard to approximate beyond the Goemans Williamson factor or if an efficient approximation algorithm exists based on whether the independent set volume exceeds this threshold.
-
Enhance Max-Cut approximation for graphs with large independent sets by using an efficient > alpha GW-approximation algorithm when the independent set volume is greater than alpha star. The system can exploit this structural property to transition from hardness results to guaranteed good performance in these instances.
-
Develop a framework for analyzing Valued PCSPs by applying the analytic methods developed in this paper, specifically the novel SDP relaxation and interval arithmetic analysis, to determine if a Max-Cut instance exhibits desirable solution properties across different evaluation methods.
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 α GW about 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.
Sources
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles