betaFeedback

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 27/29+ε≈0.93127/29+\varepsilon \approx 0.931. This improves the factor 16/17≈0.94116/17 \approx 0.941 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-kk-Cut for every kk from 4 to 20; for instance, we obtain 45/47≈0.95745/47 \approx 0.957 for Max-4-Cut and 33/34≈0.97133/34 \approx 0.971 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 Z3\mathbb{Z}_3, 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 tt and −t-t 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 27/2927/29 for Max-3-Cut. Finally, we observe that a classical reduction from Max-3-Cut to Max-kk-Cut, applied more carefully, already gives 82/85≈0.96582/85 \approx 0.965 for Max-4-Cut on 4-colourable graphs, improving the previously stated 85/8685/86.

Introduction

In Max-kk-Cut, we are given a graph with non-negative edge weights and must colour its vertices with kk colours so as to maximise the total weight of edges whose endpoints receive different colours. For k=2k = 2 this is Max-Cut. For k≥3k \ge3 the best approximation algorithms round the semidefinite relaxation of Frieze and Jerrum [6]; they achieve a ratio of about 0.836 for k=3k = 3 and 0.857 for k=4k = 4 [8 dKPW04]. For k=3k = 3 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 1−Θ(1/k)1 - \Theta(1/k), and Guruswami and Sinop [7] proved bounds of the same form even for kk-colourable graphs. The current record for k=3k = 3 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 16/17+ε16/17 + \varepsilon, even on 3-colourable graphs. Combined with a reduction of Guruswami and Sinop, the same result gives bounds for every k≥4k \ge4, such as 85/8685/86 for Max-4-Cut [2]; on kk-colourable graphs, and on general graphs for k≥5k \ge5, 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 55/57≈0.96555/57 \approx0.965, short of 16/1716/17. Table 1 collects these bounds.

on kk-colourable graphson general graphs
previous [2]Theorem 1.3previousTheorems 1.1 and 1.2
k=3k=316/17≈0.94116/17 \approx0.941—16/1716/17 [2]27/29≈0.93127/29 \approx0.931
k=4k=485/86≈0.98885/86 \approx0.98882/85≈0.96582/85 \approx0.9650.9870.987 [15]45/47≈0.95745/47 \approx0.957
k=5k=5120/121≈0.992120/121 \approx0.992119/122≈0.975119/122 \approx0.975120/121120/121 [2]33/34≈0.97133/34 \approx0.971
k=6k=6101/102≈0.990101/102 \approx0.99053/54≈0.98153/54 \approx0.981101/102101/102 [2]45/46≈0.97845/46 \approx0.978
k=7k=7136/137≈0.993136/137 \approx0.993202/205≈0.985202/205 \approx0.985136/137136/137 [2]117/119≈0.983117/119 \approx0.983

Table 1. NP-hardness of approximation for Max-kk-Cut; smaller factors are stronger. The previous values for k≥4k \ge4 are instances of the general formula 1−117(k+ck)+ck1-\frac{1}{17(k+c_k)+c_k}, ck=k mod 3c_k=k\bmod3, of [2 Thm. 1.2], except the value 0.9870.987 of [15].

Our results

Our first result improves the 16/1716/17 bound for Max-3-Cut.

Theorem 1.1. For every ε>0\varepsilon> 0 it is NP-hard, given a weighted graph GG, to distinguish between the case that some 3-colouring cuts at least a (29/30−ε)(29/30 - \varepsilon) fraction of the total edge weight and the case that every 3-colouring cuts at most a (9/10+ε)(9/10 + \varepsilon) fraction. In particular, Max-3-Cut is NP-hard to approximate within 27/29+ε≈0.93127/29 + \varepsilon\approx0.931.

The same approach, with a few extra vertices added to the gadgets, gives improved bounds for every kk.

Theorem 1.2. For every k≥3k \ge3 and ε>0\varepsilon> 0, Max-kk-Cut is NP-hard to approximate within 1−2/Γk−3+ε1 - 2/\Gamma_{k-3} + \varepsilon, where ΓL=29+18L+3(L2)\Gamma_L = 29 + 18L + 3\binom{L}{2}. In particular, Max-4-Cut is NP-hard to approximate within 45/47+ε≈0.95745/47 + \varepsilon\approx0.957, and Max-5-Cut within 33/34+ε≈0.97133/34 + \varepsilon\approx0.971.

For k=3k = 3, Theorem 1.2 is Theorem 1.1. Unlike the result of [2], our reductions do not have perfect completeness: on 3-colourable graphs, 16/1716/17 remains the best known bound. For kk-colourable graphs with k≥4k \ge4, 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 ε>0\varepsilon> 0 it is NP-hard to distinguish 4-colourable graphs from graphs in which every 4-colouring cuts at most an 82/85+ε≈0.96582/85 + \varepsilon\approx0.965 fraction of the edge weight, and 5-colourable graphs from graphs in which every 5-colouring cuts at most a 119/122+ε≈0.975119/122 + \varepsilon\approx0.975 fraction. Similar improvements hold for every kk 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-kk-Cut for every kk from 3 to 20; for larger kk the bound of [2] remains the best. All three theorems have short proofs by hand.

NP-hardness of approximation for Max-k-Cut

Figure 1. NP-hardness of approximation for Max-kk-Cut, 3≤k≤243 \le k \le24, plotted as 1−1- (hardness factor) on a logarithmic scale, so higher points are stronger bounds. The plotted values are 2/Γk−32/\Gamma_{k-3} for Theorem 1.2 (general graphs), 3/(51+34L+3(L2))3/(51+34L+3\binom{L}{2}) with L=k−3L=k-3 for Theorem 1.3 (kk-colourable graphs, k≥4k \ge4), and 1/(17(k+ck)+ck)1/(17(k+c_k)+c_k) with ck=k mod 3c_k=k\bmod3 for the previous bound of [2] (1/171/17 for k=3k=3); the diamond is the bound 0.9870.987 of [15] for Max-4-Cut. Theorem 1.2 is the strongest of the three for k≤14k \le14, Theorem 1.3 for 15≤k≤2015 \le k \le20, and [2] for k≥21k \ge21; in the shaded range k≤20k \le20 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 x1+x2+x3=tx_1+x_2+x_3=t over Z3\mathbb{Z}_3 it is NP-hard to distinguish almost satisfiable systems from systems in which every assignment satisfies at most a 1/3+ε1/3+\varepsilon 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 Z2\mathbb{Z}_2 and used for Z3\mathbb{Z}_3 by [15], replaces each equation by a small graph, a gadget (Figure 2), whose best cut is larger when the equation is satisfied. For t≠0t\ne0, however, the predicate “x1+x2+x3=tx_1+x_2+x_3=t” 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 0,1,20,1,2. In a cheating colouring all global vertices may receive the same colour, and guarding against this makes the gadgets for t≠0t\ne0 large and inefficient; in the analysis of [15] they are the bottleneck that keeps the bound above 16/1716/17.

The graph $J(\Phi)$ for a balanced role-separated instance

Figure 2. The graph J(Φ)J(\Phi) for a balanced role-separated instance Φ\Phi with three equations of weight 13\frac{1}{3}, one of each type. Each variable is a single vertex, shared by the equations that contain it (u1u_1, w2w_2 and w3w_3 occur twice). Each equation ee contributes a copy of IteI_{t_e} scaled by λe\lambda_e (box) with new auxiliary vertices (small circles, schematic); its primaries p1,p2,p3p_1,p_2,p_3 (labelled on the top copy) are identified with ueu_e, wew_e, we′w'_e (grey lines, which mark identifications and are not edges of JJ) and its globals with the shared vertices g0,…,gk−1g_0,\ldots,g_{k-1} (dashed line, drawn behind the boxes), so different copies meet only in variable vertices and globals. Section 4 decodes a colouring χ\chi into the assignment u↦a(χ(u))u \mapsto a(\chi(u)) on UU, w↦b(χ(w))w \mapsto b(\chi(w)) on WW, for arbitrary maps a,b:[k]→Z3a,b:[k]\to\mathbb{Z}_3.

The negation trick. Our main observation is that the negation −X-X of an assignment XX is again an assignment, and that −X-X satisfies an equation with right-hand side tt exactly when XX satisfies the same equation with right-hand side −t-t. If every assignment satisfies at most a 1/3+ε1/3+\varepsilon fraction of the equations, then applying this to both XX and −X-X shows that, for a random equation, the sum ss of its variables under XX satisfies s=ts=t or s=−ts=-t with probability at most about 2/3. It is therefore enough for the gadgets of the equations with t=±1t=\pm1 to detect whether s≠0s\ne0, 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 NN of Figure 4(b)). Combined with the gadget of [15] for t=0t=0, this proves Theorem 1.1 in a few lines (§ 3).

The 27 tuples $x=x_1x_2x_3\in\mathbb{Z}_3^3$ in the classes $\mathcal{A}$, $\mathcal{D}$, $\mathcal{T}_1$, and $\mathcal{T}_2$, with gadget values

Figure 3. The 27 tuples x=x1x2x3∈Z33x=x_1x_2x_3\in\mathbb{Z}_3^3 in the classes A\mathcal{A} (all equal), D\mathcal{D} (all distinct), T1\mathcal{T}_1, T2\mathcal{T}_2 (two equal, s(x)=x1+x2+x3=1s(x)=x_1+x_2+x_3=1 resp. 2); the tuples with s(x)=ts(x)=t form sat⁡t\operatorname{sat}_t, so sat⁡0=A∪D\operatorname{sat}_0=\mathcal{A}\cup\mathcal{D}, sat⁡1=T1\operatorname{sat}_1=\mathcal{T}_1 and sat⁡2=T2\operatorname{sat}_2=\mathcal{T}_2. Negation x↦−xx\mapsto-x maps A\mathcal{A} and D\mathcal{D} to themselves (on D\mathcal{D} it exchanges the two columns) and maps each tuple of T1\mathcal{T}_1 to the tuple of T2\mathcal{T}_2 at the same position (e.g. 121↦212121\mapsto212). The bottom rows give the gadget values of Theorem 3.1, with the larger value of each gadget shaded: VEV_E is larger exactly on sat⁡0\operatorname{sat}_0, and VNV_N exactly on sat⁡1∪sat⁡2\operatorname{sat}_1\cup\operatorname{sat}_2, so NN cannot tell T1\mathcal{T}_1 from T2\mathcal{T}_2.

Gadgets of Theorem 1.1 and their extensions for Max-$k$-Cut

Figure 4. Left: the gadgets of Theorem 1.1; right: their extensions for Max-kk-Cut with k=3+Lk=3+L (§ 5), drawn for L=2L=2. Thin edges have weight 1 and very thick edges weight 3; primaries are grey, the universal vertices z1,…,zLz_1,\ldots,z_L (the globals g3,…,gk−1g_3,\ldots,g_{k-1}) are squares, and edges at universal vertices are blue. (a) The type-0 gadget EE of [15], whose auxiliary vertices form the 6-cycle a1a4a5a2a3a6a_1a_4a_5a_2a_3a_6; (b) the gadget NN for types 1 and 2; (c) ALA_L adds an edge of weight 1 from every aja_j to every ziz_i (none from the primaries) and one of weight 3 between any two ziz_i; (d) NLN_L adds edges of weight 3 from every ziz_i to qq and to every primary, and none between the ziz_i.

A soundness criterion. For k≥4k\ge4 the satisfying colourings use only three of the kk 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 ρ+δ\rho+\delta for every δ>0\delta>0, where

ρ=max⁡x,y∑tVt(x,y)∑tCt\rho= \frac{\max_{x,y}\sum_t V_t(x,y)}{\sum_t C_t}

Vt(x,y)V_t(x,y) is the value of the gadget for right-hand side tt when its three variables receive the colours xx and the global vertices the colours yy, and CtC_t is its least value on satisfying colourings. In words, a cheating colouring can do no better than to use a single colour pattern xx 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 k=3k=3, 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 k=4,5k=4,5 and simplifying the solutions by hand led to the gadgets behind Theorem 1.2: the gadgets of Theorem 1.1 together with k−3k-3 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 KK-colourable graphs (KK divisible by 3) which, for K=3K=3, 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.

Distribution of $\mu^*$

Figure 5. The distribution μ∗\mu^* of the proof of Theorem 7.1. Top: one dot per tuple, at the positions of Figure 3, with area proportional to its mass (587\frac{5}{87} on each tuple of A\mathcal{A}, 129\frac{1}{29} on every other tuple); the class masses are above the boxes. Row tt: the shaded cells form sat⁡t\operatorname{sat}_t, on which Vt(x,y∘)≥CtV_t(x,y^\circ) \ge C_t; each other cell gives the probability that xrx_r lies in that class, for r∼νr \sim\nu from the type-tt certificate of Theorem 7.2. These are exactly the conditional probabilities of the classes under μ∗\mu^*, given that xx is unsatisfying for type tt. Right: the resulting lower bound on Eμ∗Vt/Ct\mathbb{E}_{\mu^*} V_t/C_t, namely μ∗(sat⁡t)\mu^*(\operatorname{sat}_t) plus the unsatisfying mass times the certificate’s guarantee ∑xθ(x)\sum_x \theta(x) (Table 2); it is 2729\frac{27}{29} 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 [k]={0,1,…,k−1}[k] = \{0,1,\ldots,k-1\} and identify [3][3] with Z3\mathbb{Z}_3. A (weighted) graph G=(V,E,w)G=(V,E,w) has non-negative edge weights; for a colouring χ:V→[k]\chi:V\to[k] let cut⁡χ(G)=∑{u,v}∈Ewuv[χ(u)≠χ(v)]\operatorname{cut}_{\chi}(G)=\sum_{\{u,v\}\in E}w_{uv}[\chi(u)\ne\chi(v)] and w(G)=∑{u,v}∈Ewuvw(G)=\sum_{\{u,v\}\in E}w_{uv}. We say that Max-kk-Cut is (c,s)(c,s)-hard if it is NP-hard to distinguish max⁡χcut⁡χ(G)≥cw(G)\max_{\chi}\operatorname{cut}_{\chi}(G)\ge c w(G) from max⁡χcut⁡χ(G)≤sw(G)\max_{\chi}\operatorname{cut}_{\chi}(G)\le s w(G); this implies NP-hardness of approximation within s/cs/c. Weights may be removed at an arbitrarily small loss by the method of [4]; see [7 Remark 2.6] for Max-kk-Cut. The transformation replaces vertices by independent sets and edges by bipartite graphs, so it also preserves kk-colourability; hence all results hold for unweighted simple graphs.

Håstad’s equations. A role-separated instance Φ\Phi of 3Lin(Z3)(\mathbb{Z}_3) consists of disjoint sets UU and WW of variables and a collection of equations ee of the form ue+we+we′=teu_e+w_e+w'_e=t_e over Z3\mathbb{Z}_3, with ue∈Uu_e\in U, distinct we,we′∈Ww_e,w'_e\in W, te∈Z3t_e\in\mathbb{Z}_3 (the type of ee), and weights λe≥0\lambda_e\ge0 summing to 1. For an assignment σ:U∪W→Z3\sigma:U\cup W\to\mathbb{Z}_3, val⁡Φ(σ)\operatorname{val}_{\Phi}(\sigma) is the total weight of the equations it satisfies, and val⁡(Φ)=max⁡σval⁡Φ(σ)\operatorname{val}(\Phi)=\max_{\sigma}\operatorname{val}_{\Phi}(\sigma). Φ\Phi is balanced if each type has total weight 1/31/3.

Theorem 2.1 (Håstad [HåS01]). For every ε>0\varepsilon>0 it is NP-hard, given a balanced role-separated instance Φ\Phi of 3Lin(Z3)(\mathbb{Z}_3), to distinguish val⁡(Φ)≥1−ε\operatorname{val}(\Phi)\ge1-\varepsilon from val⁡(Φ)≤1/3+ε\operatorname{val}(\Phi)\le1/3+\varepsilon.

Comments on the statement. This is Håstad’s theorem for the group Z3\mathbb{Z}_3 [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 UU of variables and two entries of a table indexed by a set WW 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 WW-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 u∈Uu\in U by three copies u(0),u(1),u(2)u^{(0)},u^{(1)},u^{(2)} and each equation ee by the three equations ue(c)+we+we′=te+cu_e^{(c)}+w_e+w'_e=t_e+c (c∈Z3c\in\mathbb{Z}_3), each of weight λe/3\lambda_e/3. The new instance Φ′\Phi' is role-separated (with U×Z3U\times\mathbb{Z}_3 and WW), and every type has weight exactly 1/31/3. An assignment σ\sigma of Φ\Phi yields σ(u(c))=σ(u)+c\sigma(u^{(c)})=\sigma(u)+c, which satisfies the same weight. Conversely, for any assignment τ\tau of Φ′\Phi',

val⁡Φ′(τ)=13∑c∈Z3val⁡Φ(σc),σc(u)=τ(u(c))−c,σc(w)=τ(w),\operatorname{val}_{\Phi'}(\tau)=\frac{1}{3}\sum_{c\in\mathbb{Z}_3}\operatorname{val}_{\Phi}(\sigma_c),\qquad\sigma_c(u)=\tau(u^{(c)})-c,\quad\sigma_c(w)=\tau(w),

and each σc\sigma_c is an assignment of Φ\Phi (the values on WW are shared), so val⁡(Φ′)≤val⁡(Φ)\operatorname{val}(\Phi')\le\operatorname{val}(\Phi). □

Gadgets. Fix k≥3k\ge3. A gadget II is a weighted graph on three primary vertices p1,p2,p3p_1,p_2,p_3, kk global vertices g0,…,gk−1g_0,\ldots,g_{k-1} and some auxiliary vertices. For x∈[k]3x\in[k]^3 and y∈[k]ky\in[k]^k let

VI(x,y)=max⁡{cut⁡χ(I):χ(pj)=xj, χ(gi)=yi},V_I(x,y)=\max\{\operatorname{cut}_{\chi}(I):\chi(p_j)=x_j,\ \chi(g_i)=y_i\},

the maximum being over the colours of the auxiliary vertices. Let y∘=(0,1,…,k−1)y^\circ= (0,1,\ldots,k-1) be the canonical colouring of the globals. The value of a colouring does not change when the kk colours are permuted, so we may normalise the colours of the globals: let Yk⊆[k]k\mathcal{Y}_k \subseteq[k]^k contain one representative of each orbit under permutations of the colours (we use restricted growth strings: the first entry is 00, and each entry exceeds the maximum of the previous ones by at most 11). Since VI(πx,πy)=VI(x,y)V_I(\pi x,\pi y)=V_I(x,y) for every permutation π\pi of [k][k], maxima of VIV_I, or of sums of several VIV_I, jointly over x∈[k]3x\in[k]^3 and y∈Yky\in\mathcal{Y}_k equal the maxima over x∈[k]3x\in[k]^3 and all y∈[k]ky\in[k]^k; the normalisation is only a computational saving. A family for 3Lin⁡(Z3)\operatorname{3Lin}(\mathbb{Z}_3) is a triple (I0,I1,I2)(I_0,I_1,I_2) of gadgets, ItI_t to be used for equations of type tt. We write Vt=VItV_t=V_{I_t} and Sy(x)=∑tVt(x,y)S_y(x)=\sum_t V_t(x,y). Let sat⁡t={x∈Z33:x1+x2+x3=t}\operatorname{sat}_t=\{x\in\mathbb{Z}_3^3:x_1+x_2+x_3=t\} be the set of satisfying tuples of type tt; they use only the colours 0,1,20,1,2. The completeness of ItI_t is

Ct=min⁡{Vt(x,y∘):x∈sat⁡t}.C_t=\min\{V_t(x,y^\circ):x\in\operatorname{sat}_t\}.

The reduction. Given a role-separated Φ\Phi and a family, the graph J=J(Φ)J=J(\Phi) (Figure 2) has a vertex for every variable of Φ\Phi, kk global vertices, and for every equation ee a copy of IteI_{t_e} scaled by λe\lambda_e, whose primaries p1,p2,p3p_1,p_2,p_3 are identified with ue,we,we′u_e,w_e,w'_e, whose global vertices are identified with the global vertices of JJ, and whose auxiliary vertices are new. For balanced Φ\Phi, w(J)=13∑tw(It)w(J)=\frac{1}{3}\sum_t w(I_t). If val⁡(Φ)≥1−ε\operatorname{val}(\Phi)\ge1-\varepsilon and Φ\Phi is balanced, colouring the variables by an assignment that satisfies weight at least 1−ε1-\varepsilon, the globals by y∘y^\circ, and the auxiliary vertices of each satisfied equation optimally gives

max⁡χcut⁡χ(J)≥13∑tCt−εmax⁡tCt.(1)\max_\chi\operatorname{cut}_\chi(J)\ge\frac{1}{3}\sum_t C_t-\varepsilon\max_t C_t. \tag*{(1)}

For every colouring χ\chi of JJ, after normalising y=χ(g0,…,gk−1)∈Yky=\chi(g_0,\ldots,g_{k-1})\in\mathcal{Y}_k,

cut⁡χ(J)≤∑eλeVte(χ(ue),χ(we),χ(we′),y),(2)\operatorname{cut}_\chi(J)\le\sum_e\lambda_e V_{t_e}\bigl(\chi(u_e),\chi(w_e),\chi(w'_e),y\bigr), \tag*{(2)}

since the auxiliary vertices of different copies are disjoint.

Max-3-Cut: the negation trick

Here k=3k=3, and the gadgets do not use their global vertices at all. Write s(x)=x1+x2+x3∈Z3s(x)=x_1+x_2+x_3\in\mathbb{Z}_3 and observe that s(x)=0s(x)=0 iff the three colours are all equal or all distinct, and s(x)≠0s(x)\ne0 iff exactly two of them are equal (Figure 3).

  • The EE-gadget EE (Figure 4(a)) is the type-0 gadget of [15 Lemma C.1]: auxiliary vertices a1,…,a6a_1,\ldots,a_6 and the 18 unit-weight edges

p1a1, p1a2, p1a3, p1a4, p2a3, p2a4, p2a5, p2a6, p3a1, p3a2, p3a5, p3a6,p_1a_1,\ p_1a_2,\ p_1a_3,\ p_1a_4,\ p_2a_3,\ p_2a_4,\ p_2a_5,\ p_2a_6,\ p_3a_1,\ p_3a_2,\ p_3a_5,\ p_3a_6,
a1a6, a1a4, a2a3, a2a5, a3a6, a4a5.a_1a_6,\ a_1a_4,\ a_2a_3,\ a_2a_5,\ a_3a_6,\ a_4a_5.

The auxiliary vertices form the 6-cycle a1a4a5a2a3a6a_1a_4a_5a_2a_3a_6, each is adjacent to two primaries, and opposite vertices of the cycle are adjacent to the same pair of primaries; hence EE is invariant under all permutations of the primaries.

  • The NN-gadget NN (Figure 4) consists of a unit-weight triangle on p1,p2,p3p_1,p_2,p_3 and one auxiliary vertex qq joined to p1,p2,p3p_1,p_2,p_3 by edges of weight 3 (total weight 12).

Lemma 3.1. For all x∈Z33x\in\mathbb{Z}_3^3: VE(x)=18V_E(x)=18 if s(x)=0s(x)=0 and VE(x)=16V_E(x)=16 otherwise; VN(x)=11V_N(x)=11 if s(x)≠0s(x)\ne0 and VN(x)=9V_N(x)=9 otherwise.

Proof. By symmetry under permutations of the primaries and of the colours, it suffices to consider x=(0,0,0)x=(0,0,0), x=(0,1,2)x=(0,1,2) and x=(0,0,1)x=(0,0,1). For (0,0,0)(0,0,0), colour the cycle alternately with 1 and 2; for (0,1,2)(0,1,2), give each aja_j 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 x=(0,0,1)x=(0,0,1), each of a1,a2,a5,a6a_1,a_2,a_5,a_6 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 a1a6a_1a_6 and a2a5a_2a_5 are disjoint edges, at least two edges are uncut. Colouring the cycle a1a4a5a2a3a6a_1a_4a_5a_2a_3a_6 by 2, 1, 2, 1, 2, 1 leaves exactly p3a2p_3a_2 and p3a6p_3a_6 uncut, so VE(x)=16V_E(x)=16. (This agrees with [15 Lemma C.1], which states completeness 18 and value at most 16 on unsatisfying tuples.)

For NN: if exactly two of the xjx_j are equal, the triangle contributes 2 and qq can take the third colour, contributing 9. If all are equal, the triangle contributes 0 and qq contributes 9. If all are distinct, the triangle contributes 3 and qq agrees with one primary, contributing 6. □

Proof of Theorem 1.1. Use the family (2E,N,N)(2E,N,N), i.e. EE with all weights doubled for type 0 and NN for types 1, 2. By Theorem 3.1, for every xx and every type tt,

Vt(x)=βt+2[s(x)=t]+[s(x)=−t],β0=32, β1=β2=9.(3)V_t(x)=\beta_t+2[s(x)=t]+[s(x)=-t],\qquad\beta_0=32,\ \beta_1=\beta_2=9. \tag*{(3)}

Indeed, for t=0t=0 the bracket is 2[s=0]2[s=0], and for t≠0t\ne0 it is [s≠0][s\ne0]. Let Φ\Phi be an instance from Theorem 2.1 and J=J(Φ)J=J(\Phi), so w(J)=13(36+12+12)=20w(J)=\frac{1}{3}(36+12+12)=20.

Completeness: by (1), max⁡χcut⁡χ(J)≥13(36+11+11)−36ε=583−36ε=(2930−95ε)w(J)\max_\chi\operatorname{cut}_\chi(J)\ge\frac{1}{3}(36+11+11)-36\varepsilon=\frac{58}{3}-36\varepsilon=\left(\frac{29}{30}-\frac{9}{5}\varepsilon\right)w(J).

Soundness: let χ\chi be any colouring and σ\sigma the assignment it induces on the variables of Φ\Phi. By (2) and (3),

cut⁡χ(J)≤∑eλeβte+2∑eλe([se=te]+[se=−te])=503+2(val⁡Φ(σ)+val⁡Φ(−σ)).\operatorname{cut}_\chi(J)\le\sum_e\lambda_e\beta_{t_e}+2\sum_e\lambda_e([s_e=t_e]+[s_e=-t_e])=\frac{50}{3}+2(\operatorname{val}_\Phi(\sigma)+\operatorname{val}_\Phi(-\sigma)).

where se=σ(ue)+σ(we)+σ(we′)s_e=\sigma(u_e)+\sigma(w_e)+\sigma(w'_e), because −σ-\sigma satisfies ee iff −se=te-s_e=t_e. If val⁡(Φ)≤13+ε\operatorname{val}(\Phi)\le\frac{1}{3}+\varepsilon, both values are at most 13+ε\frac{1}{3}+\varepsilon, so cut⁡χ(J)≤503+43+4ε=18+4ε=(910+15ε)w(J)\operatorname{cut}_\chi(J)\le\frac{50}{3}+\frac{4}{3}+4\varepsilon=18+4\varepsilon=\left(\frac{9}{10}+\frac{1}{5}\varepsilon\right)w(J). □

Remark 3.2. The proof of Theorem 1.1 uses neither role separation nor, essentially, balance: if the type-0 equations have total weight λ0\lambda_0 (and types 1, 2 together 1−λ01-\lambda_0), the same computation gives the ratio (23λ0+313)/(25λ0+11)≤31/33<16/17(23\lambda_0+\frac{31}{3})/(25\lambda_0+11)\le31/33<16/17. (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], NN is useless as a type-1 gadget: it does not distinguish s=1s=1 from s=2s=2, so its value on unsatisfying inputs can equal its completeness. The gain comes entirely from the analysis, which pairs σ\sigma with −σ-\sigma.

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, k≥3k\ge3.

Theorem 4.1 (Soundness criterion). Let (I0,I1,I2)(I_0,I_1,I_2) be a family of gadgets for Max-kk-Cut, k≥3k\ge3, such that each Vt(x,y)V_t(x,y) is symmetric under exchanging x2x_2 and x3x_3. Let

ρ=max⁡y∈Ykmax⁡x∈[k]3Sy(x)∑t∈Z3Ct.\rho=\frac{\max_{y\in\mathcal{Y}_k}\max_{x\in[k]^3}S_y(x)}{\sum_{t\in\mathbb{Z}_3}C_t}.

Then for every δ>0\delta>0, Max-kk-Cut is NP-hard to approximate within ρ+δ\rho+\delta. More precisely, with

wˉ=∑tw(It),\bar{w}=\sum_t w(I_t),

Max-kk-Cut is (∑tCtwˉ−δ,max⁡x,ySy(x)wˉ+δ)\left(\frac{\sum_t C_t}{\bar{w}}-\delta,\frac{\max_{x,y}S_y(x)}{\bar{w}}+\delta\right)-hard.

Proof idea. Fix a colouring χ\chi of J(Φ)J(\Phi), and let P(t,x)P(t,x) be the weight of the type-tt equations whose three variables receive the colours x∈[k]3x\in[k]^3. By (2), the cut is at most ∑t,xP(t,x)Vt(x,y)\sum_{t,x}P(t,x)V_t(x,y). If, under PP, the type tt were uniform and independent of the colour pattern xx, this would be an average of 13Sy(x)\frac{1}{3}S_y(x) over patterns, hence at most 13max⁡xSy(x)\frac{1}{3}\max_{x}S_y(x). To compare PP with such a distribution, we decode xx into assignments ϕ\phi of Φ\Phi: for any two maps a,b:[k]→Z3a,b:[k]\to\mathbb{Z}_3, a UU-variable of colour cc gets the value a(c)a(c) and a WW-variable of colour cc gets the value b(c)b(c) (Fig. 2). In the NO case $\operatorname{val}(\Phi)\le\frac{1}{3}+\epsilon of Theorem 2.1, each decoded assignment satisfies at most 13+ε\frac{1}{3}+\varepsilon, and hence (shifting aa) at least 13−2ε\frac{1}{3}-2\varepsilon, of the equations, so every test ga,bg_{a,b} defined below sees tt as nearly uniform and independent of xx. The spanning lemma (Theorem 4.2) shows that these tests detect every dependence between tt and xx that can affect the cut.

Two features of the decoding explain the hypotheses. The two WW-variables of an equation are decoded by the same map bb, so the tests cannot tell x2x_2 from x3x_3; this is why VtV_t must be symmetric in them (condition (ii) of Theorem 4.2). The UU- and WW-variables must be decoded by independent maps: the proof of Theorem 4.2 shifts aa alone by a constant cc, which changes the decoded sum by cc. If UU and WW could overlap, only maps with a=ba=b would be available, a common shift would change the sum by 3c=03c=0, and the argument would break down. This is why we need role-separated instances.

The tests. Let ω=e2πi/3\omega=e^{2\pi i/3}. For maps a,b:[k]→Z3a,b:[k]\to\mathbb{Z}_3 define ga,b:Z3×[k]3→{0,1}g_{a,b}:\mathbb{Z}_3\times[k]^3\to\{0,1\} by

ga,b(t,x)=[a(x1)+b(x2)+b(x3)=t].g_{a,b}(t,x)=\left[a(x_1)+b(x_2)+b(x_3)=t\right].

Thus ga,b(t,x)=1g_{a,b}(t,x)=1 exactly when an equation of type tt whose variables ue,we,we′u_e,w_e,w'_e have the colours x1,x2,x3x_1,x_2,x_3 is satisfied by the decoded assignment u↦a(χ(u)),w↦b(χ(w))u\mapsto a(\chi(u)), w\mapsto b(\chi(w)).

Lemma 4.2 (Spanning lemma). Let f:Z3×[k]3→Rf:\mathbb{Z}_3 \times[k]^3 \to\mathbb{R} satisfy (i) ∑t∈Z3f(t,x)=0\sum_{t\in\mathbb{Z}_3} f(t,x)=0 for every xx, and (ii) f(t,x1,x2,x3)=f(t,x1,x3,x2)f(t,x_1,x_2,x_3)=f(t,x_1,x_3,x_2). Then ff is a real linear combination of the functions ga,b−13g_{a,b}-\frac{1}{3}.

Proof. We expand ff in the characters ωℓt\omega^{\ell t} of the variable tt. By (i) the coefficient of ω0\omega^0 vanishes, and by (ii) the coefficients of ωt\omega^t and ω2t\omega^{2t} are functions of xx in Ck⊗Sym⁡2(Ck)\mathbb{C}^k\otimes\operatorname{Sym}^2(\mathbb{C}^k). We show that the products A(x1)B(x2)B(x3)A(x_1)B(x_2)B(x_3) that arise from the ga,bg_{a,b} span this space.

We work over C\mathbb{C}. For c∈Z3c\in\mathbb{Z}_3 let a+ca+c denote the map v↦a(v)+cv\mapsto a(v)+c. For fixed (t,x)(t,x), ga+c,b(t,x)=1g_{a+c,b}(t,x)=1 for exactly one cc, namely c=d:=t−a(x1)−b(x2)−b(x3)c=d:=t-a(x_1)-b(x_2)-b(x_3). Hence for ℓ∈{1,2}\ell\in\{1,2\},

hℓ,a,b:=∑c∈Z3ωℓc(ga+c,b−13)=ωℓd=ωℓtω−ℓa(x1)ω−ℓb(x2)ω−ℓb(x3).h_{\ell,a,b}:=\sum_{c\in\mathbb{Z}_3}\omega^{\ell c}\left(g_{a+c,b}-\frac{1}{3}\right)=\omega^{\ell d}=\omega^{\ell t}\omega^{-\ell a(x_1)}\omega^{-\ell b(x_2)}\omega^{-\ell b(x_3)}.

Let R⊆Ck\mathcal{R}\subseteq\mathbb{C}^k be the set of vectors whose entries are cube roots of unity. As aa and bb range over all maps, ω−ℓa(⋅)\omega^{-\ell a(\cdot)} and ω−ℓb(⋅)\omega^{-\ell b(\cdot)} range over all of R\mathcal{R} (for both ℓ=1,2\ell=1,2). Thus the span contains ωℓtA(x1)B(x2)B(x3)\omega^{\ell t}A(x_1)B(x_2)B(x_3) for all A,B∈RA,B\in\mathcal{R}.

R\mathcal{R} spans Ck\mathbb{C}^k: it contains 11 and 1+(ω−1)ei1+(\omega-1)e_i. The tensors B⊗BB\otimes B, B∈RB\in\mathcal{R}, span the symmetric square Sym⁡2(Ck)\operatorname{Sym}^2(\mathbb{C}^k): if a symmetric matrix QQ satisfies ∑i,jQijBiBj=0\sum_{i,j}Q_{ij}B_iB_j=0 for all B∈RB\in\mathcal{R}, then writing Bi=ωθiB_i=\omega^{\theta_i} this says ∑i≤jQij′ωθi+θj=0\sum_{i\leq j}Q'_{ij}\omega^{\theta_i+\theta_j}=0 for all θ∈Z3k\theta\in\mathbb{Z}_3^k, with Qii′=QiiQ'_{ii}=Q_{ii} and Qij′=2QijQ'_{ij}=2Q_{ij} for i<ji<j. The functions θ↦ωθi+θj\theta\mapsto\omega^{\theta_i+\theta_j} (i≤ji\leq j) are distinct characters of Z3k\mathbb{Z}_3^k (their exponent vectors ei+eje_i+e_j are distinct since 2≢0,1(mod3)2\not\equiv0,1\pmod{3}), hence linearly independent, so Q=0Q=0. Consequently the span contains ωℓtφ(x1)ψ(x2,x3)\omega^{\ell t}\varphi(x_1)\psi(x_2,x_3) for every φ∈Ck\varphi\in\mathbb{C}^k, every symmetric ψ∈Sym⁡2(Ck)\psi\in\operatorname{Sym}^2(\mathbb{C}^k) and ℓ=1,2\ell=1,2.

Now expand f(t,x)=∑ℓ∈Z3ωℓtf^ℓ(x)f(t,x)=\sum_{\ell\in\mathbb{Z}_3}\omega^{\ell t}\widehat{f}_\ell(x) with f^ℓ(x)=13∑tω−ℓtf(t,x)\widehat{f}_\ell(x)=\frac{1}{3}\sum_t\omega^{-\ell t}f(t,x). Condition (i) gives f^0=0\widehat{f}_0=0, and (ii) makes f^1,f^2\widehat{f}_1,\widehat{f}_2 symmetric in (x2,x3)(x_2,x_3), i.e. elements of Ck⊗Sym⁡2(Ck)\mathbb{C}^k\otimes\operatorname{Sym}^2(\mathbb{C}^k). So ff lies in the complex span of the ga,b−13g_{a,b}-\frac{1}{3}; since ff and the ga,bg_{a,b} 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 w(J)=w‾/3w(J)=\overline{w}/3. Completeness is (1). For soundness, fix y∈Yky\in\mathcal{Y}_k. The function fy(t,x)=Vt(x,y)−13Sy(x)f_y(t,x)=V_t(x,y)-\frac{1}{3}S_y(x) satisfies (i) and (ii) of Theorem 4.2, so fy=∑a,bγa,by(ga,b−13)f_y=\sum_{a,b}\gamma^y_{a,b}(g_{a,b}-\frac{1}{3}) for some reals γa,by\gamma^y_{a,b}. Let Kγ=max⁡y∑a,b∣γa,by∣K_\gamma=\max_y\sum_{a,b}|\gamma^y_{a,b}|; it depends only on the family.

Let Φ\Phi satisfy val⁡(Φ)≤13+ε\operatorname{val}(\Phi)\leq\frac{1}{3}+\varepsilon, let χ\chi be a colouring of J(Φ)J(\Phi), and normalise so that the globals have colours y∈Yky\in\mathcal{Y}_k. Let P(t,x)P(t,x) be the total weight of the equations ee with te=tt_e=t and (χ(ue),χ(we),χ(we′))=x(\chi(u_e),\chi(w_e),\chi(w'_e))=x, and let P‾(x)=∑tP(t,x)\overline{P}(x)=\sum_tP(t,x); both are probability distributions, since the weights λe\lambda_e sum to 11. For any maps a,b:[k]→Z3a,b:[k]\to\mathbb{Z}_3, the decoded assignment σa,b(u)=a(χ(u))\sigma_{a,b}(u)=a(\chi(u)) for u∈Uu\in U and σa,b(w)=b(χ(w))\sigma_{a,b}(w)=b(\chi(w)) for w∈Ww\in W is well defined because U∩W=∅U\cap W=\varnothing, and it satisfies exactly the weight ⟨P,ga,b⟩\langle P,g_{a,b}\rangle. Hence ⟨P,ga,b⟩≤13+ε\langle P,g_{a,b}\rangle\leq\frac{1}{3}+\varepsilon. Since ∑cga+c,b=1\sum_cg_{a+c,b}=1, also ⟨P,ga,b⟩=1−∑c≠0⟨P,ga+c,b⟩≥13−2ε\langle P,g_{a,b}\rangle=1-\sum_{c\ne0}\langle P,g_{a+c,b}\rangle\geq\frac{1}{3}-2\varepsilon. Therefore

cut⁡χ(J)≤∑t,xP(t,x)Vt(x,y)by xref‘(2)‘,=∑xP‾(x)Sy(x)3+∑a,bγa,by⟨P,ga,b−13⟩as Vt=13Sy+fy, expanding fy,=∑xP‾(x)Sy(x)3+∑a,bγa,by(⟨P,ga,b⟩−13)as ∑t,xP(t,x)=1,≤13max⁡xSy(x)+2Kγεas ⟨P,ga,b⟩∈[13−2ε,13+ε].\begin{aligned} \operatorname{cut}_{\chi}(J)\leq\sum_{t,x}P(t,x)V_t(x,y) \qquad\text{by {xref}`(2)`,} \\ &=\sum_x\overline{P}(x)\frac{S_y(x)}{3}+\sum_{a,b}\gamma^y_{a,b}\left\langle P,g_{a,b}-\frac{1}{3}\right\rangle \qquad\text{as }V_t=\frac{1}{3}S_y+f_y,\text{ expanding }f_y, \\ &=\sum_x\overline{P}(x)\frac{S_y(x)}{3}+\sum_{a,b}\gamma^y_{a,b}\left(\langle P,g_{a,b}\rangle-\frac{1}{3}\right) \qquad\text{as }\sum_{t,x}P(t,x)=1, \\ &\leq\frac{1}{3}\max_x S_y(x)+2K_\gamma\varepsilon \qquad\text{as }\langle P,g_{a,b}\rangle\in\left[\frac{1}{3}-2\varepsilon,\frac{1}{3}+\varepsilon\right]. \end{aligned}

Choosing ε\varepsilon small enough compared to δ\delta finishes the proof.

Tightness. The numerator of ρ\rho cannot be improved by any analysis that uses Håstad’s theorem as a black box.

Proposition 4.3. For every family, every x∗∈[k]3x^{*} \in[k]^3 and every y∗∈[k]ky^{*} \in[k]^k, there is a balanced role-separated instance Φ0\Phi_0 with val⁡Φ0(σ)=13\operatorname{val}_{\Phi_0}(\sigma) = \frac{1}{3} for every assignment σ\sigma, and a colouring of J(Φ0)J(\Phi_0) of value 13Sy∗(x∗)\frac{1}{3}S_{y^{*}}(x^{*}). Hence no soundness analysis that uses only the NO conclusion of Theorem 2.1 can improve on the numerator of ρ\rho.

Proof. Let Φ0\Phi_0 consist of one variable u∈Uu \in\mathrm{U}, two variables w,w′∈Ww,w' \in\mathrm{W} and the three equations u+w+w′=tu+w+w'=t, t∈Z3t \in\mathbb{Z}_3, of weight 13\frac{1}{3} each (or a disjoint union of copies of it). Every assignment satisfies exactly one of the three equations. Colour u,w,w′u,w,w' by x1∗,x2∗,x3∗x_1^{*},x_2^{*},x_3^{*}, the globals by y∗y^{*}, and the auxiliary vertices optimally.

In the language of the proof of Theorem 4.1, Φ0\Phi_0 realises the distribution P(t,x)=13[x=x∗]P(t,x)=\frac{1}{3}[x=x^{*}], which satisfies ⟨P,ga,b⟩=13\langle P,g_{a,b}\rangle=\frac{1}{3} for all a,ba,b and so passes every test. Moreover, if the maximum in ρ\rho is attained at some (x∗,y∗)(x^{*},y^{*}) with x2∗=x3∗x_2^{*}=x_3^{*}, then every J(Φ)J(\Phi) with Φ\Phi balanced has a colouring of value 13max⁡x,ySy(x)\frac{1}{3}\max_{x,y} S_y(x): colour all of U\mathrm{U} by x1∗x_1^{*}, all of W\mathrm{W} by x2∗x_2^{*} and the globals by y∗y^{*}. The analysis is then exact for every instance, not only for Φ0\Phi_0. 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, ρ≥αk\rho\ge\alpha_k, where αk\alpha_k 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 k=3k=3 it is never worse than the per-type analysis of [15] (Theorem A.3).

A uniform family for Max-(3+L)-Cut

Let L≥0L \ge0 and k=3+Lk=3+L. Call the global vertices g3,…,gk−1g_3,\ldots,g_{k-1} (colours 3,…,k−13,\ldots,k-1 in y∘y^{\circ}) the universal vertices z1,…,zLz_1,\ldots,z_L; the globals g0,g1,g2g_0,g_1,g_2 are not used (Figure 4(c),(Figure 4d)).

  • ALA_L: the E-gadget of Section 3 (unit weights), plus an edge of weight 1 between every auxiliary vertex aja_j and every universal vertex, plus an edge of weight 3 between every pair of universal vertices. Total weight 18+6L+3(L2)18+6L+3\binom{L}{2}.

  • NLN_L: a unit-weight triangle on the primaries, one auxiliary vertex qq joined with weight 3 to p1,p2,p3p_1,p_2,p_3 and to every universal vertex, and an edge of weight 3 between every primary and every universal vertex. Total weight 12+12L12+12L.

The family is (2AL,NL,NL)(2A_L,N_L,N_L). For L=0L=0 it is the family of Section 3.

Lemma 5.1. For every L≥0L \ge0, the gadgets ALA_L and NLN_L are invariant under all permutations of the primaries, and the family (2AL,NL,NL)(2A_L,N_L,N_L) satisfies

C0=w(2AL),C1=C2=w(NL)−1,max⁡x,ySy(x)=∑tCt−4.C_0=w(2A_L),\qquad C_1=C_2=w(N_L)-1,\qquad\max_{x,y}S_y(x)=\sum_t C_t-4.

Consequently ∑tCt=2ΓL\sum_t C_t=2\Gamma_L and ∑tw(It)=2ΓL+2\sum_t w(I_t)=2\Gamma_L+2, with ΓL=29+18L+3(L2)\Gamma_L=29+18L+3\binom{L}{2}.

Proof. For a colouring of a gadget, write col⁡(v)\operatorname{col}(v) for the colour of a vertex vv.

Completeness. Let x∈{0,1,2}3x \in\{0,1,2\}^{3} and let the globals have colours y∘y^{\circ}, so the universal vertices have distinct colours 3,…,k−13,\ldots,k-1, different from all colours of the primaries. For t=0t=0, colour the aja_j as in the proof of Theorem 3.1 (colours in {0,1,2}\{0,1,2\}): all edges of EE, all edges ajzia_jz_i and all edges zizi′z_i z_{i'} are cut, so C0=w(2AL)C_0=w(2A_L). For t≠0t\ne0, exactly two primaries are equal; colour qq by the third colour of {0,1,2}\{0,1,2\}: every edge except one triangle edge is cut, so C1=C2=w(NL)−1C_1=C_2=w(N_L)-1.

Soundness. Fix x∈[k]3x \in[k]^3 and yy, and let ℓA=w(AL)−VAL(x,y)\ell_A=w(A_L)-V_{A_L}(x,y) and ℓN=w(NL)−VNL(x,y)\ell_N=w(N_L)-V_{N_L}(x,y) be the least uncut weights. Since Sy(x)=2VAL+2VNL=∑tw(It)−2(ℓA+ℓN)=∑tCt+2−2(ℓA+ℓN)S_y(x)=2V_{A_L}+2V_{N_L}=\sum_t w(I_t)-2(\ell_A+\ell_N)=\sum_t C_t+2-2(\ell_A+\ell_N), it suffices to show ℓA+ℓN≥3\ell_A+\ell_N\ge3.

In NLN_L the vertex qq is optimally coloured with a colour that is least frequent among its neighbours, so ℓN\ell_N equals the uncut weight of the triangle, plus 33 for every pair of a primary and a universal vertex of the same colour, plus 3min⁡cnc3\min_c n_c, where ncn_c is the number of neighbours of qq (among p1,p2,p3,z1,…,zLp_1,p_2,p_3,z_1,\ldots,z_L) of colour cc. In ALA_L every pair zizi′z_i z_{i'} of equal colour costs 33. Hence we may assume that no primary shares its colour with a universal vertex, that the ziz_i have distinct colours, and that some colour is missing among the k=3+Lk=3+L neighbours of qq; otherwise ℓA≥3\ell_A\ge3 or ℓN≥3\ell_N\ge3.

If xx is constant, the triangle gives ℓN=3\ell_N=3. If x1,x2,x3x_1,x_2,x_3 are distinct, then the primaries and the ziz_i use all kk colours, which we excluded. If exactly two coincide, then by symmetry (permuting the primaries and the colours) x=(0,0,1)x=(0,0,1); the triangle gives ℓN≥1\ell_N\ge1, and exactly one colour c∗c^* lies outside {0,1,col⁡(z1),…,col⁡(zL)}\{0,1,\operatorname{col}(z_1),\ldots,\operatorname{col}(z_L)\}. Each of a1,a2,a5,a6a_1,a_2,a_5,a_6 is adjacent to a primary of colour 00, to a primary of colour 11, and to all ziz_i, so it has an uncut edge unless it has colour c∗c^*. Since a1a6a_1a_6 and a2a5a_2a_5 are disjoint edges of EE, each of the pairs {a1,a6}\{a_1,a_6\} and {a2,a5}\{a_2,a_5\} contributes an uncut edge, so ℓA≥2\ell_A\ge2. In all cases ℓA+ℓN≥3\ell_A+\ell_N\ge3.

Equality holds for constant xx and distinct universal colours different from x1x_1: then ℓN=3\ell_N=3, and the 66-cycle of EE can be coloured with the two colours outside {x1,col⁡(z1),…,col⁡(zL)}\{x_1,\operatorname{col}(z_1),\ldots,\operatorname{col}(z_L)\}, so ℓA=0\ell_A=0. Finally w(AL)=18+6L+3(L2)w(A_L)=18+6L+3\binom{L}{2} and w(NL)=12+12Lw(N_L)=12+12L give ∑tCt=2w(AL)+2w(NL)−2=2ΓL\sum_t C_t=2w(A_L)+2w(N_L)-2=2\Gamma_L.

Proof of Theorem 1.2. By Theorem 5.1 and Theorem 4.1 with w‾=2ΓL+2\overline{w}=2\Gamma_L+2, Max-kk-Cut is (2ΓL+2−δ,2ΓL−42ΓL+2+δ)\left(2\Gamma_L+2-\delta,\frac{2\Gamma_L-4}{2\Gamma_L+2}+\delta\right)-hard, and ρ=1−2/ΓL\rho=1-2/\Gamma_L. For L=0,1,2,3,4L=0,1,2,3,4, ΓL=29,47,68,92,119\Gamma_L=29,47,68,92,119.

Remark 5.2. We also confirmed Theorem 5.1 by computer, for $L\le 6 (Section B, which also lists the values for L=1L=1). 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-44-Cut and 35/3635/36 for Max-55-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 EE and NN augmented by universal vertices (the construction of § 6 applied to the gadgets of § 3), this LP returned the ratios 45/4745/47 and 33/3433/34; we then simplified the optimal solutions into the family above. Our column-generation runs for k=4,5k=4,5 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 L=1L=1) and Guruswami and Sinop [7 Sec. 2.3] (Appendix D of the arXiv version; for L≤2L\le2, where the base graph is KK-colourable with 3∣K3\mid K and the weights are dv/Kd_v/K).

Lemma 6.1. Let GG be a weighted graph with total weight MM and weighted degrees dvd_v, let L≥1L\ge1 and κ≥0\kappa\ge0. Let HH be obtained by adding vertices z1,…,zLz_1,\ldots,z_L, joining each ziz_i to every $v\in V(G)

with weight dv/3d_v/3, and joining every pair zi,zjz_i,z_j with weight κ\kappa. For a graph G′G' let unc⁡k(G′)\operatorname{unc}_k(G') be the minimum weight of monochromatic edges over kk-colourings of G′G'. Then

min⁡{κ,unc⁡3(G)}≤unc⁡3+L(H)≤unc⁡3(G),\min\{\kappa,\operatorname{unc}_3(G)\}\leq\operatorname{unc}_{3+L}(H)\leq\operatorname{unc}_3(G),

and w(H)=M(1+2L3)+(L2)κw(H)=M(1+\frac{2L}{3})+\binom{L}{2}\kappa. If GG is 3-colourable then HH is (3+L)(3+L)-colourable.

Proof. The upper bound: give z1,…,zLz_1,\ldots,z_L the colours $3,\ldots,L+2$ and colour GG optimally with {0,1,2}\{0,1,2\}. For the lower bound, let χ\chi be a (3+L)(3+L)-colouring of HH. If two ziz_i share a colour, χ\chi loses at least κ\kappa. Otherwise the ziz_i use LL distinct colours, and a vertex v∈V(G)v\in V(G) can share its colour with at most one ziz_i. If it does, the edge vzivz_i is monochromatic, of weight dv/3d_v/3. Among the three colours not used by the ziz_i, some colour is used by neighbours of vv of total weight at most $d_v/3; recolouring vv with it does not increase the weight of monochromatic edges. Repeating this for all such vv yields a colouring that uses only three colours on GG, whose monochromatic weight is at least unc⁡3(G)\operatorname{unc}_3(G). The total weight follows from ∑vdv=2M\sum_v d_v=2M.

If GG comes from a (c,s)(c,s)-hard instance of Max-3-Cut with Δc=1−c\Delta_c=1-c and Δs=1−s\Delta_s=1-s, choose κ=ΔsM\kappa=\Delta_sM, so that w(H)=mLMw(H)=m_LM with mLm_L as in (4). Then unc⁡3+L(H)≤ΔcM\operatorname{unc}_{3+L}(H)\leq\Delta_cM in the YES case and ≥ΔsM\geq\Delta_sM in the NO case, so Max-(3+L)(3+L)-Cut is hard within

mL−ΔsmL−Δc,mL=1+2L3+(L2)Δs.(4)\frac{m_L-\Delta_s}{m_L-\Delta_c},\qquad m_L=1+\frac{2L}{3}+\binom{L}{2}\Delta_s. \tag*{(4)}

Proof of Theorem 1.3. Apply (4) to the (1,1617+ε)(1,\frac{16}{17}+\varepsilon)-hardness of 3-colouring of [2] (Δc=0\Delta_c=0, Δs=117\Delta_s=\frac{1}{17}): the ratio is 1−ΔsmL=1−151+34L+3(L2)1-\frac{\Delta_s}{m_L}=1-\frac{1}{51+34L+3\binom{L}{2}}, e.g. 8285\frac{82}{85} for L=1L=1 and 119122\frac{119}{122} for L=2L=2. Perfect completeness is preserved.

A barrier for gadgets from 3Lin(Z3\mathbb{Z}_3) 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(Z2\mathbb{Z}_2).

Theorem 7.1 (computer-assisted). For every family (I0,I1,I2)(I_0,I_1,I_2) of Max-3-Cut gadgets (with any number of auxiliary vertices, possibly using the global vertices),

max⁡x∈Z33Sy∘(x)≥2729∑tCt.\max_{x\in\mathbb{Z}_3^3} S_y^{\circ}(x)\geq\frac{27}{29}\sum_t C_t.

Hence Theorem 4.1 cannot give a ratio below 27/2927/29 for Max-3-Cut, and the family of § 3 is optimal for it.

The proof exhibits a single distribution μ∗\mu^* on Z33\mathbb{Z}_3^3 such that, for every type tt and every type-tt gadget, the average of Vt(x,y∘)V_t(x,y^\circ) over x∼μ∗x\sim\mu^* is at least 2729Ct\frac{27}{29}C_t. Summing over tt gives the theorem, since the maximum of Sy∘S_{y^\circ} is at least its average.

The distribution μ∗\mu^*. Partition Z33\mathbb{Z}_3^3 into the classes A\mathcal{A} (all equal, 3 tuples), D\mathcal{D} (all distinct, 6 tuples), T1\mathcal{T}_1 and T2\mathcal{T}_2 (two equal with sum 1, resp. 2; 9 tuples each), as in Figure 3, so that sat⁡0=A∪D\operatorname{sat}_0=\mathcal{A}\cup\mathcal{D}, sat⁡1=T1\operatorname{sat}_1=\mathcal{T}_1 and sat⁡2=T2\operatorname{sat}_2=\mathcal{T}_2. Let μ∗\mu^* be uniform within each class, with class masses in the proportions

μ∗(A):μ∗(D):μ∗(T1):μ∗(T2)=5:6:9:9,\mu^*(\mathcal{A}) : \mu^*(\mathcal{D}) : \mu^*(\mathcal{T}_1) : \mu^*(\mathcal{T}_2) = 5 : 6 : 9 : 9,

that is, mass 529\frac{5}{29} on A\mathcal{A} and 129\frac{1}{29} on every other tuple (Figure 5). A type-tt gadget is guaranteed its completeness value CtC_t on sat⁡t\operatorname{sat}_t. On the unsatisfying tuples we use a certificate (Theorem 7.2) that guarantees on average a fraction 89\frac{8}{9} of C0C_0 for type 0 and 910\frac{9}{10} of CtC_t for t=1,2t=1,2 (Table 2), but only for one particular distribution of inputs: uniform on T1∪T2\mathcal{T}_1\cup\mathcal{T}_2 for type 0, and in the proportions 5:6:95:6:9 on A,D,T2\mathcal{A},\mathcal{D},\mathcal{T}_2 for type 1 (on A,D,T1\mathcal{A},\mathcal{D},\mathcal{T}_1 for type 2). These requirements determine μ∗\mu^*: 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 Eμ∗Vt/Ct\mathbb{E}_{\mu^*}V_t/C_t, namely μ∗(sat⁡t)\mu^*(\operatorname{sat}_t) plus the unsatisfying mass times the certificate’s fraction:

1129+1829⋅89=929+2029⋅910=2729.\frac{11}{29}+\frac{18}{29}\cdot\frac{8}{9}=\frac{9}{29}+\frac{20}{29}\cdot\frac{9}{10}=\frac{27}{29}.

Certificates. The bounds on the unsatisfying tuples are instances of weak LP duality.

Lemma 7.2. Fix tt and let Ft=[3]sat⁡tF_t=[3]^{\operatorname{sat}_t} be the set of columns (functions from sat⁡t\operatorname{sat}_t to colours). Suppose θ:sat⁡t→R≥0\theta:\operatorname{sat}_t\to\mathbb{R}_{\ge0} and a probability distribution ν\nu over pairs r=(xr,χr)r=(x_r,\chi_r), with xr∈Z33x_r\in\mathbb{Z}_3^3 and χr\chi_r a colouring of the universe Ω={p1,p2,p3,g0,g1,g2}∪Ft\Omega=\{p_1,p_2,p_3,g_0,g_1,g_2\}\cup F_t with χr(pj)=(xr)j\chi_r(p_j)=(x_r)_j and χr(gi)=i\chi_r(g_i)=i, satisfy, for every pair {ξ,η}⊆Ω\{\xi,\eta\}\subseteq\Omega,

Pr⁡r∼ν[χr(ξ)≠χr(η)]≥∑x∈sat⁡tθ(x)[can⁡x(ξ)≠can⁡x(η)],(5)\Pr_{r\sim\nu}[\chi_r(\xi)\ne\chi_r(\eta)]\ge\sum_{x\in\operatorname{sat}_t}\theta(x)[\operatorname{can}_x(\xi)\ne\operatorname{can}_x(\eta)], \tag*{(5)}

where can⁡x\operatorname{can}_x is the canonical colouring of Ω\Omega at xx: can⁡x(pj)=xj\operatorname{can}_x(p_j)=x_j, can⁡x(gi)=i\operatorname{can}_x(g_i)=i, can⁡x(f)=f(x)\operatorname{can}_x(f)=f(x). Then every type-tt gadget satisfies Er∼νVt(xr,y∘)≥(∑xθ(x))Ct\mathbb{E}_{r\sim\nu}V_t(x_r,y^\circ)\ge\left(\sum_x\theta(x)\right)C_t.

Proof. For each x∈sat⁡tx\in\operatorname{sat}_t fix a colouring of the auxiliary vertices of ItI_t attaining Vt(x,y∘)≥CtV_t(x,y^\circ)\ge C_t. Let ϕ:V(It)→Ω\phi:V(I_t)\to\Omega map pjp_j and gig_i to themselves and each auxiliary vertex to its column (its colour

type ttsat⁡t\operatorname{sat}_{t}distribution of xrx_{r} (by class)∑xθ(x)\sum_{x}\theta(x)rowscommon denominator
0A∪D\mathcal{A}\cup\mathcal{D}uniform on T1∪T2\mathcal{T}_{1}\cup\mathcal{T}_{2}8/98/978324
1T1\mathcal{T}_{1}A,D,T2\mathcal{A},\mathcal{D},\mathcal{T}_{2} in proportions 5:6:95:6:99/109/101624680
2T2\mathcal{T}_{2}A,D,T1\mathcal{A},\mathcal{D},\mathcal{T}_{1} in proportions 5:6:95:6:99/109/101624680

caption: The certificates of Theorem 7.2 used for Theorem 7.1. In each, xrx_{r} is uniform within each class and never satisfying; “rows” is the number of pairs rr (the rows of the certificate) with positive weight under ν\nu, and the last column is the common denominator of the stored exact certificate (Section B).

:::

as a function of xx). Then can⁡x∘ϕ\operatorname{can}_{x}\circ\phi is the fixed optimal colouring at xx, and χr∘ϕ\chi_{r}\circ\phi is a colouring with primaries xrx_{r} and globals y∘y^{\circ}, of value at most Vt(xr,y∘)V_{t}(x_{r},y^{\circ}). Summing (5) over the edges ξ′η′\xi'\eta' of ItI_{t} with ϕ(ξ′)≠ϕ(η′)\phi(\xi')\ne\phi(\eta'), with their non-negative weights, gives ErVt(xr,y∘)≥∑xθ(x)Vt(x,y∘)≥(∑xθ(x))Ct\mathbb{E}_{r}V_{t}(x_{r},y^{\circ})\ge\sum_{x}\theta(x)V_{t}(x,y^{\circ})\ge(\sum_{x}\theta(x))C_{t}; edges with ϕ(ξ′)=ϕ(η′)\phi(\xi')=\phi(\eta') are never cut by can⁡x∘ϕ\operatorname{can}_{x}\circ\phi.

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 II, let I′I' be II with g1g_{1} and g2g_{2} exchanged. By invariance under the colour permutation c↦−cc\mapsto-c, VI′(x,y∘)=VI(−x,y∘)V_{I'}(x,y^{\circ})=V_{I}(-x,y^{\circ}), so I′I' is a type-1 gadget with the same completeness, and the type-1 certificate gives EVI(−xr,y∘)≥910CI\mathbb{E}V_{I}(-x_{r},y^{\circ})\ge\frac{9}{10}C_{I}, where −xr-x_{r} 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 xrx_{r} is the conditional distribution of μ∗\mu^{*} on the complement of sat⁡t\operatorname{sat}_{t}. Hence, since Vt(x,y∘)≥CtV_{t}(x,y^{\circ})\ge C_{t} on sat⁡t\operatorname{sat}_{t},

Eμ∗V0≥1129C0+1829⋅89C0=2729C0,Eμ∗V1≥929C1+2029⋅910C1=2729C1,\mathbb{E}_{\mu^{*}}V_{0}\ge\frac{11}{29}C_{0}+\frac{18}{29}\cdot\frac{8}{9}C_{0}=\frac{27}{29}C_{0},\qquad \mathbb{E}_{\mu^{*}}V_{1}\ge\frac{9}{29}C_{1}+\frac{20}{29}\cdot\frac{9}{10}C_{1}=\frac{27}{29}C_{1},

and likewise for V2V_{2}. Summing over tt, max⁡xSy∘(x)≥Eμ∗Sy∘(x)≥2729∑tCt\max_{x}S_{y^{\circ}}(x)\ge\mathbb{E}_{\mu^{*}}S_{y^{\circ}}(x)\ge\frac{27}{29}\sum_{t}C_{t}.

Remark 7.3. In each row rr of the certificates, the colour of a column ff is hr(f∣Rr)h_{r}(f\mathbin{|}R_{r}) for a set RrR_{r} of one or two satisfying tuples and a table hr:[3]Rr→[3]h_{r}:[3]^{R_{r}}\to[3]. 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 Ω\Omega (∣Ft∣=39|F_{t}|=3^{9}), 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 ∑iaixi=t\sum_{i}a_{i}x_{i}=t over Z3\mathbb{Z}_{3} with a∈{±1}ra\in\{\pm1\}^{r} and ∑iai≡0\sum_{i}a_{i}\equiv0, 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 2Lin⁡(Z2)2\operatorname{Lin}(\mathbb{Z}_{2}) [11]. We expect the proof of Theorem 4.1 to carry over to Chan’s rr-partite instances, with one decoding map per player (the analogue of Theorem 4.2 for products of rr arbitrary vectors), in which case no symmetry hypothesis would be needed.

  • Optimality for k≥4k \ge4. We do not know whether 45/4745/47 and 33/3433/34 are optimal under Theorem 4.1; our column generation found nothing better, but we have no barrier certificate.

  • Large kk. Our family gives 1−Θ(1/k2)1-\Theta(1/k^2); combining Theorem 4.1 with the tensor construction of [7] might improve the constant in 1−Θ(1/k)1-\Theta(1/k) and the range k≤20k \le20 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 ItI_t by It′=12It⊔12ItswI'_t=\frac{1}{2}I_t\sqcup\frac{1}{2}I_t^{\mathrm{sw}}, where ItswI_t^{\mathrm{sw}} is ItI_t with p2,p3p_2,p_3 exchanged and ⊔\sqcup takes disjoint copies of the auxiliary vertices while sharing primaries and globals. Then Vt′(x,y)=12(Vt(x,y)+Vt(x1,x3,x2,y))V'_t(x,y)=\frac{1}{2}(V_t(x,y)+V_t(x_1,x_3,x_2,y)), so no CtC_t decreases (the satisfying sets are symmetric) and max⁡x,ySy(x)\max_{x,y}S_y(x) 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 a≡c1a\equiv c_1, b≡c2b\equiv c_2 the soundness hypothesis in fact forces every type to have weight 13±O(ε)\frac{1}{3}\pm O(\varepsilon).

Remark A.3 (Comparison with the per-type analysis). For k=3k=3, Theorem 4.1 is never worse than the per-type analysis. Every x∈Z33x\in\mathbb{Z}_3^3 satisfies exactly one type t(x)t(x), so Sy(x)≤Vt(x)++∑t≠t(x)Vt−S_y(x)\le V^+_{t(x)}+\sum_{t\ne t(x)}V^-_t, where Vt+V^+_t and Vt−V^-_t are the maxima of VtV_t over satisfying resp. unsatisfying xx and all yy; hence ρ≤(∑tVt−+max⁡t(Vt+−Vt−))/∑tCt\rho\le(\sum_tV^-_t+\max_t(V^+_t-V^-_t))/\sum_tC_t, which is the bound of the per-type reduction theorem [15 Thm. C.2]. With Vt+=CtV^+_t=C_t and Vt−=Ct−dV^-_t=C_t-d this is 1−2d/∑tCt1-2d/\sum_tC_t. 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-kk-CUT, ρ≥αk\rho\ge\alpha_k, where αk\alpha_k is the approximation ratio of the Frieze–Jerrum rounding [6 dKPW04].

Proof. Let ζ0,…,ζk−1\zeta_0,\ldots,\zeta_{k-1} be unit vectors with ⟨ζc,ζc′⟩=−1k−1\langle\zeta_c,\zeta_{c'}\rangle=-\frac{1}{k-1} for c≠c′c\ne c'. For each tt and each satisfying tuple xx of type tt (there are 99), fix a colouring χxt\chi_x^t of ItI_t with primaries xx, globals y∘y^\circ and value Vt(x,y∘)≥CtV_t(x,y^\circ)\ge C_t, and let vξt=(9−1/2ζχxt(ξ))xv_\xi^t=(9^{-1/2}\zeta_{\chi_x^t(\xi)})_x for each vertex ξ\xi of ItI_t. These are unit vectors with ⟨vξt,vξ′t⟩=1−kk−1Pr⁡x[χxt(ξ)≠χxt(ξ′)]≥−1k−1\langle v_\xi^t,v_{\xi'}^t\rangle=1-\frac{k}{k-1}\Pr_x[\chi_x^t(\xi)\ne\chi_x^t(\xi')]\ge-\frac{1}{k-1}, and their Frieze–Jerrum objective ∑wξξ′k−1k(1−⟨vξt,vξ′t⟩)\sum w_{\xi\xi'}\frac{k-1}{k}(1-\langle v_\xi^t,v_{\xi'}^t\rangle) equals ExVt(x,y∘)≥Ct\mathbb{E}_xV_t(x,y^\circ)\ge C_t. On the set BB of primary and global vertices, the disagreement probabilities do not depend on tt (any two primaries are independent and uniform on {0,1,2}\{0,1,2\}), so the Gram matrix of (vξt)ξ∈B(v_\xi^t)_{\xi\in B} is the same for all tt. Fix vectors (fξ)ξ∈B(f_\xi)_{\xi\in B} in some Rm\mathbb{R}^m with this Gram matrix, let Ψt\Psi_t be the isometry from span⁡{vξt:ξ∈B}\operatorname{span}\{v_\xi^t:\xi\in B\} onto span⁡{fξ}\operatorname{span}\{f_\xi\} with vξt↦fξv_\xi^t\mapsto f_\xi, and Πt\Pi_t the orthogonal projection onto the former span. In a direct sum Rm⊕H0⊕H1⊕H2\mathbb{R}^m\oplus H_0\oplus H_1\oplus H_2 put v~ξ=ΨtΠtvξt+ut(vξt−Πtv~ξ)\widetilde v_\xi=\Psi_t\Pi_tv_\xi^t+u_t(v_\xi^t-\Pi_t\widetilde v_\xi) for ξ\xi in ItI_t, where utu_t embeds into HtH_t. Then v~ξ=fξ\widetilde v_\xi=f_\xi on BB and all inner products within each ItI_t are preserved, so this is a vector solution for I0∪I1∪I2I_0\cup I_1\cup I_2 (glued along BB) with objective at least ∑tCt\sum_tC_t, in which every edge has inner product ≥−1k−1\ge-\frac{1}{k-1}. (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 αkk−1k(1−⟨v~ξ,v~ξ′⟩)\alpha_k\frac{k-1}{k}(1-\langle\widetilde v_\xi,\widetilde v_{\xi'}\rangle), so some colouring has value at least αk∑tCt\alpha_k\sum_tC_t; but every colouring has value at most max⁡x,ySy(x)\max_{x,y}S_y(x).

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 Vt(x,y)V_t(x,y) for all x∈[k]3x \in[k]^3 and y∈Yky \in\mathcal{Y}_k by exhaustive enumeration of the auxiliary colourings in integer arithmetic, checks the symmetry hypothesis of Theorem 4.1, and outputs the exact ratio ρ\rho; it reproduces Theorem 5.1 for L≤3L \le3. The independently written scripts/independent/family_dp.py (which optimises the auxiliary vertices of ALA_L by dynamic programming along the 6-cycle) reproduces it for L≤6L \le6. For L=1L = 1, Table 3 lists the values by the pattern of equalities among x1,x2,x3x_1,x_2,x_3 and col⁡(z1)\operatorname{col}(z_1); the remaining patterns follow by permuting the primaries and the colours.

(x1,x2,x3∣col⁡(z1))(x_1,x_2,x_3 \mid\operatorname{col}(z_1))(0,0,0∣0)(0,0,0 \mid0)(0,0,0∣1)(0,0,0 \mid1)(0,0,1∣0)(0,0,1 \mid0)(0,0,1∣1)(0,0,1 \mid1)(0,0,1∣2)(0,0,1 \mid2)(0,1,2∣0)(0,1,2 \mid0)(0,1,2∣3)(0,1,2 \mid3)
V2A1V_{2A_1}48484848444848
VN1V_{N_1}12211720232121
S=V2A1+2VN1S = V_{2A_1} + 2V_{N_1}72908288909090

Table 3. Gadget values of the family (2A1,N1,N1)(2A_1,N_1,N_1) for Max-4-Cut (L=1L = 1), 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(Z3\mathbb{Z}_3) 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-tt 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 ctc_t; soundness is enforced by variables vt(x,y)v_t(x,y) with rows vt(x,y)≥v_t(x,y) \ge (value of an explicit colouring), generated by local search and verified by exact separation, and coupling rows τ≥∑tvt(x,y)\tau\ge\sum_t v_t(x,y) for all (x,y)(x,y); we minimise τ\tau subject to ∑tct≥1\sum_t c_t \ge1. New auxiliary vertices were generated by exact dual pricing of single vertices (over all 494^9 columns for k=4k = 4) and by pricing whole small gadgets with up to 7 auxiliary vertices; in our runs the optimum stayed at 45/4745/47 (k=4k = 4) and 33/3433/34 (k=5k = 5). Barrier certificates. The certificates of Theorem 7.1 are stored as exact integers (common denominator DD, row weights, θ\theta, and for each row xrx_r, RrR_r, hrh_r) 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 θ≥0\theta\ge0, that ν\nu is a probability distribution whose marginal on xrx_r is uniform within each class, that ∑θ\sum\theta equals 89\frac{8}{9} resp. 910\frac{9}{10}, and verifies (5) for all pairs of elements of Ω\Omega, including all (92)\binom{9}{2} pairs of columns, with integer-valued floating-point matrix products whose partial sums stay below 2532^{53} (hence exact). A second, independently written checker (check_exact_pairwise.py) writes the slack of a pair of columns (f,f′)(f,f') as a sum of unary and pairwise terms in the nine pairs (f(x),f′(x))(f(x),f'(x)), x∈sattx \in\mathrm{sat}_t, and minimises it exactly over all 999^9 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. [1]Per Austrin and Elchanan Mossel. Approximation resistant predicates from pairwise independence. Computational Complexity, 18(2):249–271, 2009.
  2. [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. [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. [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
  5. [6]Alan Frieze and Mark Jerrum. Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Algorithmica, 18(1):67–81, 1997.
  6. [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.
  7. [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.
  8. [9]Johan Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798–859, 2001.
  9. [10]Steven Heilman. Sharp hardness for MAX-3-CUT and quantum MAX-CUT. arXiv:2608.00333, 2026.arxiv.org/abs/2608.00333
  10. [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.
  11. [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
  12. [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.
  13. [14]Alexander Novikov et al. AlphaEvolve: A coding agent for scientific and algorithmic discovery. arXiv:2506.13131, 2025.arxiv.org/abs/2506.13131
  14. [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
  15. [16]Erez Petrank. The hardness of approximation: gap location. Computational Complexity, 4(2):133–157, 1994.
  16. [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.

Paper details

vlnc:W_u3bv92y9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents