WorksComputer Science
Improved NP-Hardness of Approximation for Max-3-Cut and for Max-k-Cut with Small k
Abstract
We prove that Max-3-Cut is NP-hard to approximate within a factor of . This improves the factor of Austrin, O'Donnell, Tan and Wright, the best NP-hardness result for Max-3-Cut since 2012. (Their result, unlike ours, also holds for 3-colourable graphs.) We also improve the NP-hardness of Max--Cut for every from 4 to 20; for instance, we obtain for Max-4-Cut and for Max-5-Cut, where the previous factors were 0.987 and 120/121. Our reductions are gadget reductions from Håstad's linear equations over , with gadgets that have at most six auxiliary vertices. The main new idea is a negation trick: since the negation of an assignment is again an assignment, equations with right-hand sides and can be handled together, and this makes the resulting predicates symmetric under all permutations of the colours. We complement it with a general soundness criterion for such reductions: in effect, the best strategy of the adversary is to use a single colour pattern everywhere. This criterion is the strongest analysis that uses Håstad's theorem as a black box, and, using LP duality, we show that under it no gadget reduction from these equations can beat for Max-3-Cut. Finally, we observe that a classical reduction from Max-3-Cut to Max--Cut, applied more carefully, already gives for Max-4-Cut on 4-colourable graphs, improving the previously stated .
Introduction
In Max--Cut, we are given a graph with non-negative edge weights and must colour its vertices with colours so as to maximise the total weight of edges whose endpoints receive different colours. For this is Max-Cut. For the best approximation algorithms round the semidefinite relaxation of Frieze and Jerrum [6]; they achieve a ratio of about 0.836 for and 0.857 for [8 dKPW04]. For this is optimal under the Unique Games Conjecture [12, 10].
Much less is known about NP-hardness. Kann, Khanna, Lagergren and Panconesi [13] proved hardness of the form , and Guruswami and Sinop [7] proved bounds of the same form even for -colourable graphs. The current record for was set by Austrin, O’Donnell, Tan and Wright [2]: using a PCP designed for the purpose, they showed that Max-3-Cut is NP-hard to approximate within , even on 3-colourable graphs. Combined with a reduction of Guruswami and Sinop, the same result gives bounds for every , such as for Max-4-Cut [2]; on -colourable graphs, and on general graphs for , these are the best previously stated bounds. Most recently, Nagda, Raghavan and Thakurta [15] used the AlphaEvolve system [14] to search for gadget reductions from H˚astad’s linear equations [9]. This improved the bound for Max-4-Cut to about 0.987, but for Max-3-Cut their gadgets give only , short of . Table 1 collects these bounds.
Table 1. NP-hardness of approximation for Max--Cut; smaller factors are stronger. The previous values for are instances of the general formula , , of [2 Thm. 1.2], except the value of [15].
Our results
Our first result improves the bound for Max-3-Cut.
Theorem 1.1. For every it is NP-hard, given a weighted graph , to distinguish between the case that some 3-colouring cuts at least a fraction of the total edge weight and the case that every 3-colouring cuts at most a fraction. In particular, Max-3-Cut is NP-hard to approximate within .
The same approach, with a few extra vertices added to the gadgets, gives improved bounds for every .
Theorem 1.2. For every and , Max--Cut is NP-hard to approximate within , where . In particular, Max-4-Cut is NP-hard to approximate within , and Max-5-Cut within .
For , Theorem 1.2 is Theorem 1.1. Unlike the result of [2], our reductions do not have perfect completeness: on 3-colourable graphs, remains the best known bound. For -colourable graphs with , however, we observe that the bounds previously stated in the literature can also be improved, by applying a known reduction more carefully.
Theorem 1.3. For every it is NP-hard to distinguish 4-colourable graphs from graphs in which every 4-colouring cuts at most an fraction of the edge weight, and 5-colourable graphs from graphs in which every 5-colouring cuts at most a fraction. Similar improvements hold for every from 4 to 20 (§ 6).
Table 1 and Figure 1 compare our bounds with the previous ones. Together, Theorems 1.2 and 1.3 improve the best known NP-hardness of Max--Cut for every from 3 to 20; for larger the bound of [2] remains the best. All three theorems have short proofs by hand.

Figure 1. NP-hardness of approximation for Max--Cut, , plotted as (hardness factor) on a logarithmic scale, so higher points are stronger bounds. The plotted values are for Theorem 1.2 (general graphs), with for Theorem 1.3 (-colourable graphs, ), and with for the previous bound of [2] ( for ); the diamond is the bound of [15] for Max-4-Cut. Theorem 1.2 is the strongest of the three for , Theorem 1.3 for , and [2] for ; in the shaded range this paper improves the best previous bound.
Overview of the techniques
Gadget reductions and the colour-reference problem. Håstad [Hås01] proved that for systems of equations over it is NP-hard to distinguish almost satisfiable systems from systems in which every assignment satisfies at most a fraction of the equations. The classical way to turn this into hardness for a graph problem, introduced by Trevisan, Sorkin, Sudan and Williamson [17] for and used for by [15], replaces each equation by a small graph, a gadget (Figure 2), whose best cut is larger when the equation is satisfied. For , however, the predicate “” is not invariant under renaming the colours, so its gadget must refer to a fixed set of global vertices that play the role of the colours . In a cheating colouring all global vertices may receive the same colour, and guarding against this makes the gadgets for large and inefficient; in the analysis of [15] they are the bottleneck that keeps the bound above .

Figure 2. The graph for a balanced role-separated instance with three equations of weight , one of each type. Each variable is a single vertex, shared by the equations that contain it (, and occur twice). Each equation contributes a copy of scaled by (box) with new auxiliary vertices (small circles, schematic); its primaries (labelled on the top copy) are identified with , , (grey lines, which mark identifications and are not edges of ) and its globals with the shared vertices (dashed line, drawn behind the boxes), so different copies meet only in variable vertices and globals. Section 4 decodes a colouring into the assignment on , on , for arbitrary maps .
The negation trick. Our main observation is that the negation of an assignment is again an assignment, and that satisfies an equation with right-hand side exactly when satisfies the same equation with right-hand side . If every assignment satisfies at most a fraction of the equations, then applying this to both and shows that, for a random equation, the sum of its variables under satisfies or with probability at most about 2/3. It is therefore enough for the gadgets of the equations with to detect whether , which simply means that exactly two of the three variables are equal (Figure 3). This predicate is invariant under all permutations of the colours, needs no global vertices, and is detected by a triangle together with one extra vertex (the gadget of Figure 4(b)). Combined with the gadget of [15] for , this proves Theorem 1.1 in a few lines (§ 3).

Figure 3. The 27 tuples in the classes (all equal), (all distinct), , (two equal, resp. 2); the tuples with form , so , and . Negation maps and to themselves (on it exchanges the two columns) and maps each tuple of to the tuple of at the same position (e.g. ). The bottom rows give the gadget values of Theorem 3.1, with the larger value of each gadget shaded: is larger exactly on , and exactly on , so cannot tell from .

Figure 4. Left: the gadgets of Theorem 1.1; right: their extensions for Max--Cut with (§ 5), drawn for . Thin edges have weight 1 and very thick edges weight 3; primaries are grey, the universal vertices (the globals ) are squares, and edges at universal vertices are blue. (a) The type-0 gadget of [15], whose auxiliary vertices form the 6-cycle ; (b) the gadget for types 1 and 2; (c) adds an edge of weight 1 from every to every (none from the primaries) and one of weight 3 between any two ; (d) adds edges of weight 3 from every to and to every primary, and none between the .
A soundness criterion. For the satisfying colourings use only three of the colours, and global vertices become necessary again. We prove a general criterion for gadget reductions from Håstad’s equations (Theorem 4.1): under a mild symmetry condition, the gadgets give NP-hardness of approximation within for every , where
is the value of the gadget for right-hand side when its three variables receive the colours and the global vertices the colours , and is its least value on satisfying colourings. In words, a cheating colouring can do no better than to use a single colour pattern on all equations, and each pattern is charged with the sum of the values of all three gadgets. The proof decodes a colouring of the graph into many assignments of Håstad’s instance and uses a short Fourier-analytic argument; it relies on the fact that Håstad’s equations have one variable of one kind and two of another. We also show that no analysis that uses Håstad’s theorem only as a black box can do better (Theorem 4.3). The criterion contains the negation trick and, for , the analysis of [15] as special cases. It also turns gadget design into a single linear program over the three gadgets. Solving this program for and simplifying the solutions by hand led to the gadgets behind Theorem 1.2: the gadgets of Theorem 1.1 together with global vertices of the extra colours (§ 5).
Universal vertices. Theorem 1.3 uses a reduction of [13, 7] that adds vertices joined to the whole graph and forces them to take the extra colours. The previously stated constants apply it on top of a general bound for -colourable graphs ( divisible by 3) which, for , is three times weaker than the 16/17 bound it is derived from; applying it directly to the 16/17 bound gives Theorem 1.3 (§ 6). Placing the extra vertices inside the gadgets, as in Theorem 1.2, is more economical than adding them to the final graph.
A barrier. Finally, we show that 27/29 is the best factor that the criterion can give for Max-3-Cut, for gadgets of any size (Theorem 7.1): there is a single distribution of colour patterns on which every gadget, for every right-hand side, still achieves at least a 27/29 fraction of its completeness value on average (Figure 5). The proof uses LP duality, in the spirit of the optimality proofs of [17, 11], with explicit rational certificates that we verify by computer in exact arithmetic; this is the only computer-assisted result of the paper. To go beyond 27/29, one has to change the source problem (for instance, to other predicates covered by Chan’s theorem [3]), the form of the reduction, or the analysis.

Figure 5. The distribution of the proof of Theorem 7.1. Top: one dot per tuple, at the positions of Figure 3, with area proportional to its mass ( on each tuple of , on every other tuple); the class masses are above the boxes. Row : the shaded cells form , on which ; each other cell gives the probability that lies in that class, for from the type- certificate of Theorem 7.2. These are exactly the conditional probabilities of the classes under , given that is unsatisfying for type . Right: the resulting lower bound on , namely plus the unsatisfying mass times the certificate’s guarantee (Table 2); it is for every type.
How these results were obtained. This research was carried out with extensive use of an AI system, which designed and ran the computer searches, found the arguments and drafted the paper under the direction of the author. The methodology, including how every claim was checked, is described in Section B and in the AI methodology statement at the end of the paper.
Organisation. Section 2 fixes notation and states Håstad’s theorem in the form we use. Section 3 proves Theorem 1.1, Section 4 the soundness criterion, and Section 5 Theorem 1.2. Section 6 treats universal vertices and Theorem 1.3, Section 7 the barrier, and Section 8 open problems. Section A collects further remarks on the soundness criterion, and Section B describes the computations.
Preliminaries
Cuts. We write and identify with . A (weighted) graph has non-negative edge weights; for a colouring let and . We say that Max--Cut is -hard if it is NP-hard to distinguish from ; this implies NP-hardness of approximation within . Weights may be removed at an arbitrarily small loss by the method of [4]; see [7 Remark 2.6] for Max--Cut. The transformation replaces vertices by independent sets and edges by bipartite graphs, so it also preserves -colourability; hence all results hold for unweighted simple graphs.
Håstad’s equations. A role-separated instance of 3Lin consists of disjoint sets and of variables and a collection of equations of the form over , with , distinct , (the type of ), and weights summing to 1. For an assignment , is the total weight of the equations it satisfies, and . is balanced if each type has total weight .
Theorem 2.1 (Håstad [HåS01]). For every it is NP-hard, given a balanced role-separated instance of 3Lin, to distinguish from .
Comments on the statement. This is Håstad’s theorem for the group [HåS01, Thm. 5.9]; the gap version follows from Lemmas 5.10 and 5.11 there. In his verifier, each test reads one entry of a folded long-code table indexed by a set of variables and two entries of a table indexed by a set of clauses, and accepts iff the three values sum to a constant; folding only changes the right-hand side. Giving the two provers separate tables makes the instance role-separated; the soundness analysis [HåS01, Lemma 5.11] applies to arbitrary tables, i.e. to arbitrary assignments, and constructs the strategies of the two provers from the two kinds of tables separately. Tests whose two -entries fall into the same folded class have negligible total weight (it tends to 0 with the parameter of the verifier); we discard them, which changes completeness and soundness by a negligible amount.
To balance the types, replace every by three copies and each equation by the three equations (), each of weight . The new instance is role-separated (with and ), and every type has weight exactly . An assignment of yields , which satisfies the same weight. Conversely, for any assignment of ,
and each is an assignment of (the values on are shared), so . □
Gadgets. Fix . A gadget is a weighted graph on three primary vertices , global vertices and some auxiliary vertices. For and let
the maximum being over the colours of the auxiliary vertices. Let be the canonical colouring of the globals. The value of a colouring does not change when the colours are permuted, so we may normalise the colours of the globals: let contain one representative of each orbit under permutations of the colours (we use restricted growth strings: the first entry is , and each entry exceeds the maximum of the previous ones by at most ). Since for every permutation of , maxima of , or of sums of several , jointly over and equal the maxima over and all ; the normalisation is only a computational saving. A family for is a triple of gadgets, to be used for equations of type . We write and . Let be the set of satisfying tuples of type ; they use only the colours . The completeness of is
The reduction. Given a role-separated and a family, the graph (Figure 2) has a vertex for every variable of , global vertices, and for every equation a copy of scaled by , whose primaries are identified with , whose global vertices are identified with the global vertices of , and whose auxiliary vertices are new. For balanced , . If and is balanced, colouring the variables by an assignment that satisfies weight at least , the globals by , and the auxiliary vertices of each satisfied equation optimally gives
For every colouring of , after normalising ,
since the auxiliary vertices of different copies are disjoint.
Max-3-Cut: the negation trick
Here , and the gadgets do not use their global vertices at all. Write and observe that iff the three colours are all equal or all distinct, and iff exactly two of them are equal (Figure 3).
The -gadget (Figure 4(a)) is the type-0 gadget of [15 Lemma C.1]: auxiliary vertices and the 18 unit-weight edges
The auxiliary vertices form the 6-cycle , each is adjacent to two primaries, and opposite vertices of the cycle are adjacent to the same pair of primaries; hence is invariant under all permutations of the primaries.
The -gadget (Figure 4) consists of a unit-weight triangle on and one auxiliary vertex joined to by edges of weight 3 (total weight 12).
Lemma 3.1. For all : if and otherwise; if and otherwise.
Proof. By symmetry under permutations of the primaries and of the colours, it suffices to consider , and . For , colour the cycle alternately with 1 and 2; for , give each the colour of the primary it is not adjacent to (consecutive vertices of the cycle then differ). In both cases all 18 edges are cut. For , each of is adjacent to a primary of colour 0 and one of colour 1, so it has an uncut edge unless it has colour 2; since and are disjoint edges, at least two edges are uncut. Colouring the cycle by 2, 1, 2, 1, 2, 1 leaves exactly and uncut, so . (This agrees with [15 Lemma C.1], which states completeness 18 and value at most 16 on unsatisfying tuples.)
For : if exactly two of the are equal, the triangle contributes 2 and can take the third colour, contributing 9. If all are equal, the triangle contributes 0 and contributes 9. If all are distinct, the triangle contributes 3 and agrees with one primary, contributing 6. □
Proof of Theorem 1.1. Use the family , i.e. with all weights doubled for type 0 and for types 1, 2. By Theorem 3.1, for every and every type ,
Indeed, for the bracket is , and for it is . Let be an instance from Theorem 2.1 and , so .
Completeness: by (1), .
Soundness: let be any colouring and the assignment it induces on the variables of . By (2) and (3),
where , because satisfies iff . If , both values are at most , so . □
Remark 3.2. The proof of Theorem 1.1 uses neither role separation nor, essentially, balance: if the type-0 equations have total weight (and types 1, 2 together ), the same computation gives the ratio . (For role-separated instances the soundness hypothesis even forces balance in the NO case, see Theorem A.2.)
Remark 3.3. In the per-type framework of [15, 17], is useless as a type-1 gadget: it does not distinguish from , so its value on unsatisfying inputs can equal its completeness. The gain comes entirely from the analysis, which pairs with .
A soundness criterion for gadgets from Håstad's equations
This section proves the criterion behind Theorems 1.2 and 7.1. Readers interested only in Max-3-Cut may skip it: Theorem 1.1 was proved directly in Section 3, and Sections 5 and 7 use only the statement of Theorem 4.1. Throughout, .
Theorem 4.1 (Soundness criterion). Let be a family of gadgets for Max--Cut, , such that each is symmetric under exchanging and . Let
Then for every , Max--Cut is NP-hard to approximate within . More precisely, with
Max--Cut is -hard.
Proof idea. Fix a colouring of , and let be the weight of the type- equations whose three variables receive the colours . By (2), the cut is at most . If, under , the type were uniform and independent of the colour pattern , this would be an average of over patterns, hence at most . To compare with such a distribution, we decode into assignments of : for any two maps , a -variable of colour gets the value and a -variable of colour gets the value (Fig. 2). In the NO case $\operatorname{val}(\Phi)\le\frac{1}{3}+\epsilon of Theorem 2.1, each decoded assignment satisfies at most , and hence (shifting ) at least , of the equations, so every test defined below sees as nearly uniform and independent of . The spanning lemma (Theorem 4.2) shows that these tests detect every dependence between and that can affect the cut.
Two features of the decoding explain the hypotheses. The two -variables of an equation are decoded by the same map , so the tests cannot tell from ; this is why must be symmetric in them (condition (ii) of Theorem 4.2). The - and -variables must be decoded by independent maps: the proof of Theorem 4.2 shifts alone by a constant , which changes the decoded sum by . If and could overlap, only maps with would be available, a common shift would change the sum by , and the argument would break down. This is why we need role-separated instances.
The tests. Let . For maps define by
Thus exactly when an equation of type whose variables have the colours is satisfied by the decoded assignment .
Lemma 4.2 (Spanning lemma). Let satisfy (i) for every , and (ii) . Then is a real linear combination of the functions .
Proof. We expand in the characters of the variable . By (i) the coefficient of vanishes, and by (ii) the coefficients of and are functions of in . We show that the products that arise from the span this space.
We work over . For let denote the map . For fixed , for exactly one , namely . Hence for ,
Let be the set of vectors whose entries are cube roots of unity. As and range over all maps, and range over all of (for both ). Thus the span contains for all .
spans : it contains and . The tensors , , span the symmetric square : if a symmetric matrix satisfies for all , then writing this says for all , with and for . The functions () are distinct characters of (their exponent vectors are distinct since ), hence linearly independent, so . Consequently the span contains for every , every symmetric and .
Now expand with . Condition (i) gives , and (ii) makes symmetric in , i.e. elements of . So lies in the complex span of the ; since and the are real, taking real parts of the coefficients gives a real combination.
Proof of Theorem 4.1. Reduce from Theorem 2.1 as in § 2; then . Completeness is (1). For soundness, fix . The function satisfies (i) and (ii) of Theorem 4.2, so for some reals . Let ; it depends only on the family.
Let satisfy , let be a colouring of , and normalise so that the globals have colours . Let be the total weight of the equations with and , and let ; both are probability distributions, since the weights sum to . For any maps , the decoded assignment for and for is well defined because , and it satisfies exactly the weight . Hence . Since , also . Therefore
Choosing small enough compared to finishes the proof.
Tightness. The numerator of cannot be improved by any analysis that uses Håstad’s theorem as a black box.
Proposition 4.3. For every family, every and every , there is a balanced role-separated instance with for every assignment , and a colouring of of value . Hence no soundness analysis that uses only the NO conclusion of Theorem 2.1 can improve on the numerator of .
Proof. Let consist of one variable , two variables and the three equations , , of weight each (or a disjoint union of copies of it). Every assignment satisfies exactly one of the three equations. Colour by , the globals by , and the auxiliary vertices optimally.
In the language of the proof of Theorem 4.1, realises the distribution , which satisfies for all and so passes every test. Moreover, if the maximum in is attained at some with , then every with balanced has a colouring of value : colour all of by , all of by and the globals by . The analysis is then exact for every instance, not only for . This is the case for all families in this paper, where the maximum is attained at a constant tuple.
Further properties. The criterion is consistent with the known algorithms: for every family, , where is the approximation ratio of the Frieze–Jerrum rounding [6 dKPW04] (Theorem A.4). Section A also shows that the symmetry hypothesis of Theorem 4.1 costs nothing (Theorem A.1), that the theorem does not need balance in the NO case (Theorem A.2), and that for it is never worse than the per-type analysis of [15] (Theorem A.3).
A uniform family for Max-(3+L)-Cut
Let and . Call the global vertices (colours in ) the universal vertices ; the globals are not used (Figure 4(c),(Figure 4d)).
: the E-gadget of Section 3 (unit weights), plus an edge of weight 1 between every auxiliary vertex and every universal vertex, plus an edge of weight 3 between every pair of universal vertices. Total weight .
: a unit-weight triangle on the primaries, one auxiliary vertex joined with weight 3 to and to every universal vertex, and an edge of weight 3 between every primary and every universal vertex. Total weight .
The family is . For it is the family of Section 3.
Lemma 5.1. For every , the gadgets and are invariant under all permutations of the primaries, and the family satisfies
Consequently and , with .
Proof. For a colouring of a gadget, write for the colour of a vertex .
Completeness. Let and let the globals have colours , so the universal vertices have distinct colours , different from all colours of the primaries. For , colour the as in the proof of Theorem 3.1 (colours in ): all edges of , all edges and all edges are cut, so . For , exactly two primaries are equal; colour by the third colour of : every edge except one triangle edge is cut, so .
Soundness. Fix and , and let and be the least uncut weights. Since , it suffices to show .
In the vertex is optimally coloured with a colour that is least frequent among its neighbours, so equals the uncut weight of the triangle, plus for every pair of a primary and a universal vertex of the same colour, plus , where is the number of neighbours of (among ) of colour . In every pair of equal colour costs . Hence we may assume that no primary shares its colour with a universal vertex, that the have distinct colours, and that some colour is missing among the neighbours of ; otherwise or .
If is constant, the triangle gives . If are distinct, then the primaries and the use all colours, which we excluded. If exactly two coincide, then by symmetry (permuting the primaries and the colours) ; the triangle gives , and exactly one colour lies outside . Each of is adjacent to a primary of colour , to a primary of colour , and to all , so it has an uncut edge unless it has colour . Since and are disjoint edges of , each of the pairs and contributes an uncut edge, so . In all cases .
Equality holds for constant and distinct universal colours different from : then , and the -cycle of can be coloured with the two colours outside , so . Finally and give .
Proof of Theorem 1.2. By Theorem 5.1 and Theorem 4.1 with , Max--Cut is -hard, and . For , .
Remark 5.2. We also confirmed Theorem 5.1 by computer, for $L\le 6 (Section B, which also lists the values for ). Placing the universal vertices inside the gadgets is more economical than adding them to the final graph as in § 6: combining Theorem 1.1 with Theorem 6.1 gives only $47/49$ for Max--Cut and for Max--Cut.
Remark 5.3 (How the family was found). Theorem 4.1 makes the design of a family a single linear program (Section B). Seeded with and augmented by universal vertices (the construction of § 6 applied to the gadgets of § 3), this LP returned the ratios and ; we then simplified the optimal solutions into the family above. Our column-generation runs for did not find better families.
Universal vertices and perfect completeness
The following reduction is due to Kann, Khanna, Lagergren and Panconesi [13 Sec. 3] (for ) and Guruswami and Sinop [7 Sec. 2.3] (Appendix D of the arXiv version; for , where the base graph is -colourable with and the weights are ).
Lemma 6.1. Let be a weighted graph with total weight and weighted degrees , let and . Let be obtained by adding vertices , joining each to every $v\in V(G)
with weight , and joining every pair with weight . For a graph let be the minimum weight of monochromatic edges over -colourings of . Then
and . If is 3-colourable then is -colourable.
Proof. The upper bound: give the colours $3,\ldots,L+2$ and colour optimally with . For the lower bound, let be a -colouring of . If two share a colour, loses at least . Otherwise the use distinct colours, and a vertex can share its colour with at most one . If it does, the edge is monochromatic, of weight . Among the three colours not used by the , some colour is used by neighbours of of total weight at most $d_v/3; recolouring with it does not increase the weight of monochromatic edges. Repeating this for all such yields a colouring that uses only three colours on , whose monochromatic weight is at least . The total weight follows from .
If comes from a -hard instance of Max-3-Cut with and , choose , so that with as in (4). Then in the YES case and in the NO case, so Max--Cut is hard within
Proof of Theorem 1.3. Apply (4) to the -hardness of 3-colouring of [2] (, ): the ratio is , e.g. for and for . Perfect completeness is preserved.
A barrier for gadgets from 3Lin() to Max-3-Cut
Optimality proofs for gadgets via LP duality go back to [17]; [11] proved an analogous optimality statement for gadgets from Chan’s Hadamard predicates to 2Lin().
Theorem 7.1 (computer-assisted). For every family of Max-3-Cut gadgets (with any number of auxiliary vertices, possibly using the global vertices),
Hence Theorem 4.1 cannot give a ratio below for Max-3-Cut, and the family of § 3 is optimal for it.
The proof exhibits a single distribution on such that, for every type and every type- gadget, the average of over is at least . Summing over gives the theorem, since the maximum of is at least its average.
The distribution . Partition into the classes (all equal, 3 tuples), (all distinct, 6 tuples), and (two equal with sum 1, resp. 2; 9 tuples each), as in Figure 3, so that , and . Let be uniform within each class, with class masses in the proportions
that is, mass on and on every other tuple (Figure 5). A type- gadget is guaranteed its completeness value on . On the unsatisfying tuples we use a certificate (Theorem 7.2) that guarantees on average a fraction of for type 0 and of for (Table 2), but only for one particular distribution of inputs: uniform on for type 0, and in the proportions on for type 1 (on for type 2). These requirements determine : it is the only distribution, uniform within each class, whose conditional distribution on the unsatisfying tuples of each type is that of the certificate. With these masses all three types end at the same lower bound on , namely plus the unsatisfying mass times the certificate’s fraction:
Certificates. The bounds on the unsatisfying tuples are instances of weak LP duality.
Lemma 7.2. Fix and let be the set of columns (functions from to colours). Suppose and a probability distribution over pairs , with and a colouring of the universe with and , satisfy, for every pair ,
where is the canonical colouring of at : , , . Then every type- gadget satisfies .
Proof. For each fix a colouring of the auxiliary vertices of attaining . Let map and to themselves and each auxiliary vertex to its column (its colour
| type | distribution of (by class) | rows | common denominator | ||
| 0 | uniform on | 78 | 324 | ||
| 1 | in proportions | 162 | 4680 | ||
| 2 | in proportions | 162 | 4680 |
caption: The certificates of Theorem 7.2 used for Theorem 7.1. In each, is uniform within each class and never satisfying; “rows” is the number of pairs (the rows of the certificate) with positive weight under , and the last column is the common denominator of the stored exact certificate (Section B).
:::
as a function of ). Then is the fixed optimal colouring at , and is a colouring with primaries and globals , of value at most . Summing (5) over the edges of with , with their non-negative weights, gives ; edges with are never cut by .
Proof of Theorem 7.1. We use certificates as in Theorem 7.2 with the parameters of Table 2. The type-2 certificate is obtained from the type-1 certificate by symmetry: for a type-2 gadget , let be with and exchanged. By invariance under the colour permutation , , so is a type-1 gadget with the same completeness, and the type-1 certificate gives , where is distributed as in the last row of Table 2. (We also stored and checked this mirrored certificate explicitly.)
In each certificate, the distribution of is the conditional distribution of on the complement of . Hence, since on ,
and likewise for . Summing over , .
Remark 7.3. In each row of the certificates, the colour of a column is for a set of one or two satisfying tuples and a table . The certificates were found by solving the dual LP with constraint generation over pairs, and then rounded to rationals (Table 2). The rounded certificates are what is verified: (5) was checked exactly, for all pairs of elements of (), by two programs using different methods; the minimum slack is 0 (Section B).
Discussion
Perfect completeness. Our reductions lose completeness (29/30); on 3-colourable graphs 16/17 [2] is still the best bound (the first constant bound there is due to [16]). Can the negation trick be combined with a source that has perfect completeness?
Other sources. By Theorem 7.1 and Theorem 4.3, per-type gadgets on the instances of Theorem 2.1, analysed through Theorem 2.1 alone, cannot beat 27/29. Natural candidates for other sources are the predicates over with and , which are NP-hard to approximate by Chan’s theorem [Chal16] (the unconditional analogue of [1]) and for which the negation trick again yields colour-symmetric predicates; gadget reductions from Chan’s predicates have been used successfully for [11]. We expect the proof of Theorem 4.1 to carry over to Chan’s -partite instances, with one decoding map per player (the analogue of Theorem 4.2 for products of arbitrary vectors), in which case no symmetry hypothesis would be needed.
Optimality for . We do not know whether and are optimal under Theorem 4.1; our column generation found nothing better, but we have no barrier certificate.
Large . Our family gives ; combining Theorem 4.1 with the tensor construction of [7] might improve the constant in and the range in which we improve the known bounds.
Further remarks on the soundness criterion
Remark A.1 (The symmetry hypothesis). The symmetry hypothesis of Theorem 4.1 is harmless: replace by , where is with exchanged and takes disjoint copies of the auxiliary vertices while sharing primaries and globals. Then , so no decreases (the satisfying sets are symmetric) and does not increase. Gadgets that are symmetric under all permutations of the primaries, as all gadgets in this paper, satisfy the hypothesis trivially.
Remark A.2 (Balance). The proof of Theorem 4.1 does not use that the types are balanced in the NO case; with constant maps , the soundness hypothesis in fact forces every type to have weight .
Remark A.3 (Comparison with the per-type analysis). For , Theorem 4.1 is never worse than the per-type analysis. Every satisfies exactly one type , so , where and are the maxima of over satisfying resp. unsatisfying and all ; hence , which is the bound of the per-type reduction theorem [15 Thm. C.2]. With and this is . Theorem 4.1 can be much better because a tuple that is unsatisfying for two types need not be bad for both gadgets simultaneously.
Proposition A.4. For every family for MAX--CUT, , where is the approximation ratio of the Frieze–Jerrum rounding [6 dKPW04].
Proof. Let be unit vectors with for . For each and each satisfying tuple of type (there are ), fix a colouring of with primaries , globals and value , and let for each vertex of . These are unit vectors with , and their Frieze–Jerrum objective equals . On the set of primary and global vertices, the disagreement probabilities do not depend on (any two primaries are independent and uniform on ), so the Gram matrix of is the same for all . Fix vectors in some with this Gram matrix, let be the isometry from onto with , and the orthogonal projection onto the former span. In a direct sum put for in , where embeds into . Then on and all inner products within each are preserved, so this is a vector solution for (glued along ) with objective at least , in which every edge has inner product . (Auxiliary vertices of different gadgets are not adjacent, so their inner products do not matter.) The rounding of [6 dKPW04] cuts each such edge with probability at least , so some colouring has value at least ; but every colouring has value at most .
Methodology and computations
How the results were obtained. The research was carried out with an AI system (Claude, by Anthropic) working in an agentic coding environment, under the direction of the author, who set the goals at each stage (first improving the gadgets of [15] for Max-4-Cut and Max-5-Cut, then attacking Max-3-Cut) and decided which directions to pursue. The AI system wrote and ran the linear-programming searches for gadgets and the verification programs, proposed the negation trick of § 3 while exploring alternative source problems, derived the soundness criterion of § 4, found the gadget families of § 5 (by the linear program described below, followed by simplification) and the hand proof of Theorem 5.1, observed the consequences of the universal-vertex reduction in § 6, computed the certificates of Section 7, searched the literature, and drafted the text. Every main claim was checked in two ways. First, independently instantiated AI agents, which did not see the reasoning that produced a claim, were asked to refute it: they re-read the primary sources (in particular Håstad’s verifier and the constants of [7, 2]), re-derived the proofs, and re-implemented the computations from scratch; four such referees also reviewed a draft of this paper. Second, every gadget value and every certificate was verified by at least two independently written programs, all using exact arithmetic, as described below.
Availability. The code, the gadget families and the certificates are available at https://github.com/ziangni-sys/max-3-cut. All programs are in Python 3 with NumPy; HiGHS was used for the linear programs.
Verification of families. scripts/verify_sum_criterion.py, applied to the families produced by scripts/make_unified_family.py, computes for all and by exhaustive enumeration of the auxiliary colourings in integer arithmetic, checks the symmetry hypothesis of Theorem 4.1, and outputs the exact ratio ; it reproduces Theorem 5.1 for . The independently written scripts/independent/family_dp.py (which optimises the auxiliary vertices of by dynamic programming along the 6-cycle) reproduces it for . For , Table 3 lists the values by the pattern of equalities among and ; the remaining patterns follow by permuting the primaries and the colours.
| 48 | 48 | 48 | 48 | 44 | 48 | 48 | |
| 12 | 21 | 17 | 20 | 23 | 21 | 21 | |
| 72 | 90 | 82 | 88 | 90 | 90 | 90 |
Table 3. Gadget values of the family for Max-4-Cut (), by colour pattern.
scripts/verify_sym3.py checks Theorem 3.1 and the identity (3); the end-to-end reduction of § 3 was also tested on random small instances of 3LIN() by brute force.
The design LP. For fixed candidate auxiliary vertices, each described by its column (its colour in the completeness colouring at each satisfying tuple), each type- block has one variable per orbit of edges under permutations of the primaries. Completeness rows require the canonical colouring at each satisfying tuple to have value at least ; soundness is enforced by variables with rows (value of an explicit colouring), generated by local search and verified by exact separation, and coupling rows for all ; we minimise subject to . New auxiliary vertices were generated by exact dual pricing of single vertices (over all columns for ) and by pricing whole small gadgets with up to 7 auxiliary vertices; in our runs the optimum stayed at () and (). Barrier certificates. The certificates of Theorem 7.1 are stored as exact integers (common denominator , row weights, , and for each row , , ) in the files cert_t0.json, cert_t1.json and cert_t2.json of the directory results/barrier_k3. The checker check_exact.py verifies that , that is a probability distribution whose marginal on is uniform within each class, that equals resp. , and verifies (5) for all pairs of elements of , including all pairs of columns, with integer-valued floating-point matrix products whose partial sums stay below (hence exact). A second, independently written checker (check_exact_pairwise.py) writes the slack of a pair of columns as a sum of unary and pairwise terms in the nine pairs , , and minimises it exactly over all choices of these pairs. Both find minimum slack 0.
Universal vertices. scripts/universal_vertex.py checks Theorem 6.1 by brute force on random weighted graphs and computes (4).
AI methodology
We used Claude (Anthropic), a large language model, in an agentic coding environment (Claude Code, including multi-agent workflows), to carry out this research and to write this paper. The tool proposed the main ideas (the negation trick, the soundness criterion and its proof, the gadget families and the proof of Theorem 5.1, the use of the universal-vertex reduction, and the barrier certificates), wrote and ran all search and verification programs, performed the literature search, and drafted the text of all sections. It therefore materially affected all sections of the paper; the methodology, including how the claims were checked by independent AI agents and by independent programs, is described in Section B. The author directed the research and is responsible for the content of the submission. The author verified the correctness and originality of all content, including references.
References
- [1]Per Austrin and Elchanan Mossel. Approximation resistant predicates from pairwise independence. Computational Complexity, 18(2):249–271, 2009.
- [2]Per Austrin, Ryan O’Donnell, Li-Yang Tan, and John Wright. New NP-hardness results for 3-coloring and 2-to-1 label cover. ACM Transactions on Computation Theory, 6(1):Article 2, 2014. arXiv:1210.5648.arxiv.org/abs/1210.5648
- [3]Siu On Chan. Approximation resistance from pairwise-independent subgroups. Journal of the ACM, 63(3):Article 27, 2016. Preliminary version in STOC 2013.
- [4]Pierluigi Crescenzi, Riccardo Silvestri, and Luca Trevisan. On weighted vs unweighted versions of combinatorial optimization problems. Information and Computation, 167(1):10–26, 2001.DOI
- [6]Alan Frieze and Mark Jerrum. Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Algorithmica, 18(1):67–81, 1997.
- [7]Venkatesan Guruswami and Ali Kemal Sinop. Improved inapproximability results for maximum k-colorable subgraph. Theory of Computing, 9(11):413–435, 2013. Preliminary version in APPROX 2009; arXiv:0910.2271.
- [8]Michel X. Goemans and David P. Williamson. Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. Journal of Computer and System Sciences, 68(2):442–470, 2004. Preliminary version in STOC 2001.
- [9]Johan Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798–859, 2001.
- [10]Steven Heilman. Sharp hardness for MAX-3-CUT and quantum MAX-CUT. arXiv:2608.00333, 2026.arxiv.org/abs/2608.00333
- [11]Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O’Donnell, and John Wright. Improved NP-inapproximability for 2-variable linear equations. Theory of Computing, 13(19):1–51, 2017. Preliminary version in APPROX 2015.
- [12]Marcus Isaksson and Elchanan Mossel. Maximally stable Gaussian partitions with discrete applications. Israel Journal of Mathematics, 189:347–396, 2012.arxiv.org/abs/0903.3362
- [13]Viggo Kann, Sanjeev Khanna, Jens Lagergren, and Alessandro Panconesi. On the hardness of approximating Max k-Cut and its dual. Chicago Journal of Theoretical Computer Science, 1997:Article 2, 1997. Preliminary version in ISTCS 1996.
- [14]Alexander Novikov et al. AlphaEvolve: A coding agent for scientific and algorithmic discovery. arXiv:2506.13131, 2025.arxiv.org/abs/2506.13131
- [15]Ansh Nagda, Prabhakar Raghavan, and Abhradeep Thakurta. Reinforced generation of combinatorial structures: Hardness of approximation. arXiv:2509.18057, 2025. Version 7, March 2026.arxiv.org/abs/2509.18057
- [16]Erez Petrank. The hardness of approximation: gap location. Computational Complexity, 4(2):133–157, 1994.
- [17]Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson. Gadgets, approximation, and linear programming. SIAM Journal on Computing, 29(6):2074–2097, 2000.