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

arXiv:2604.10318 · cs.DS · Submitted 2026-04-11 · Read on arXiv

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

Where the paper says it

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.

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

Where the paper says it

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.

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. p. 0
Where the paper says it

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.

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. p. 6
Where the paper says it

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.

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

Where the paper says it

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].

The analysis also utilizes Fourier analysis and Gaussian noise stability bounds, such as Theorem 3. p. 2
Where the paper says it

1 Fourier Analysis . 2 Gaussian Noise Stability .

4, to establish the required bounds for the soundness guarantee. p. 8
Where the paper says it

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.

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

Where the paper says it

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 ).

4 and Lemma 8. p. 2
Where the paper says it

5 Overview of the Algorithm . 6 Proof Sketch of Lemma 2.

8 to show that the expected cut size is greater than arccos ρ∗ π. p. 5
Where the paper says it

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 ρ ∗ .

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

Where the paper says it

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.

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

Where the paper says it

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.

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

Where the paper says it

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 ρ ∗ .

3 provides a general lemma (Lemma A. p. 9
Where the paper says it

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) used to prove the completeness guarantee for the reduction. p. 9
Where the paper says it

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.

These proofs use interval arithmetic verification to establish approximation guarantees. p. 3
Where the paper says it

3 Influence Decoding Lemma . 52 B Some Derivatives for Interval Arithmetic Verification 53 2

The paper also details partial derivatives of correlation functions and noise stability bounds, such as Lemma B. p. 2
Where the paper says it

2 Gaussian Noise Stability . 3 Correlation and Noise Stability .

1, which are used in the final analysis. p. 9
Where the paper says it

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 ρ ∗ .

The interval arithmetic code will be made available in the de-anonymized version of this paper. p. 1
Where the paper says it

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.

The verification code is based on the Arb library [Joh17]. p. 0
Where the paper says it

– For any graph that contains an independent set of size > α ∗ , there exists an efficient > αGW-approximation algorithm for Max-Cut. *Companion code: https://github.

The paper also details heuristics for constructing a piecewise linear threshold function t in Table 1. p. 4
Where the paper says it

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].

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

  1. 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.

  2. 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.

  3. 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