An 83/8483/84 approximation for a cubic three-occurrence Horn class

Primarily AI-generated textHuman understanding: all partscs.CC — Computational Complexitycs.DS — Data Structures and Algorithms

Contributed by Frank Vega ↗

Version 1 / Nov 21, 2026 / CC BY 4.0

Abstract

We study an unweighted MAX-HORN-2SAT class, which is also a class of MAX 2-SAT instances, in which every Boolean variable has exactly three literal occurrences. For a simple cubic graph H=(V,E)H=(V,E) the formula THT_H satisfies OPT⁡(TH)=4∣V∣+∣E∣+α(H)\operatorname{OPT}(T_H)=4|V|+|E|+\alpha(H), and every assignment of value AA is repaired in polynomial time to an independent set of size at least A−(4∣V∣+∣E∣)A-(4|V|+|E|). This gives a polynomial-time 83/8483/84 approximation from a cubic independent-set approximation and a near-bipartite cut algorithm, an LL-reduction from cubic MIS, and APX-completeness. For simple dd-regular graphs the optimum is (d+1)∣V∣+∣E∣+α(H)(d+1)|V|+|E|+\alpha(H) and the factors are: (3d+2)/(3d+3)(3d+2)/(3d+3) from the all-true assignment, which is at least 83/8483/84 for d≥27d\ge27; 83/8483/84 from the Berman--Fujito guarantee for d≥22d\ge22 and, with a semidefinite cut rounding, for d=21d=21; and (21d+20)/(21d+21)(21d+20)/(21d+21) from any 6/76/7-approximate independent set. For arbitrary simple graphs the optimum is n+3m+α(H)n+3m+\alpha(H). MAX-CUT on a dd-regular graph GG reduces to MAX 2-SAT with the clauses (xu∨xv)(x_u\vee x_v) and (¬xu∨¬xv)(\neg x_u\vee\neg x_v) per edge, of value m+cut⁡(S)m+\operatorname{cut}(S). The conflict graph H(G)H(G) is (d+1)(d+1)-regular and α(H(G))=m+maxcut⁡(G)\alpha(H(G))=m+\operatorname{maxcut}(G). A Goemans--Williamson cut gives on TH(G)T_{H(G)} the factor 1−1−αε6d+12≥83/841-\frac{1-\alpha_\varepsilon}{6d+12}\ge83/84 for every d≥1d\ge1, and a γ\gamma-dependent analysis gives 1−0.10536d+11.51-\frac{0.1053}{6d+11.5}, where αε=αGW−10−5\alpha_\varepsilon=\alpha_{\mathrm{GW}}-10^{-5} and γ=maxcut⁡(G)/m\gamma=\operatorname{maxcut}(G)/m. For arbitrary simple graphs without isolated vertices the factor exceeds 0.99320.9932. A cut guarantee cdc_d on graphs of maximum degree dd gives 1−1−cd6d+121-\frac{1-c_d}{6d+12}, which exceeds 0.99770.9977 in expectation for d=3d=3. A ratio on TH(G)T_{H(G)} and a cut guarantee are equivalent, so the cut recovered is the Goemans--Williamson or bounded-degree cut used, and the MAX-CUT guarantee is not improved. The main consequence is that on the class {TH(G)}\{T_{H(G)}\} of three-occurrence Horn formulas obtained from MAX-CUT instances the proved factor 83/8483/84 exceeds the Unique Games thresholds ≈0.94616\approx0.94616 and ≈0.94017\approx0.94017 that hold for all instances of weighted MAX-HORN-2SAT and of MAX 2-SAT. For a restricted hard-split family with unit vertex rewards and edge-clause weights at least one we obtain 27/2827/28, and 257/260257/260 with edge weights four. The Unique Games thresholds of Brakensiek--Huang--Zwick (≈0.94616\approx0.94616), Lewin--Livnat--Zwick (≈0.94017\approx0.94017) for MAX 2-SAT, and Khot--Kindler--Mossel--O'Donnell (≈0.87856\approx0.87856) for MAX-CUT quantify over all instances; the guarantees above concern classes with three occurrences per variable, exceed the first two thresholds, and are consistent with the conjecture. Max-Ones 2-SAT for negative (Horn) formulas equals Maximum Independent Set and Min-Ones 2-SAT for positive formulas equals Minimum Vertex Cover, with the same optima, so the published hardness of these two problems applies to them, and OPT⁡(TH)=4∣V∣+∣E∣+MaxOnes⁡(NH)\operatorname{OPT}(T_H)=4|V|+|E|+\operatorname{MaxOnes}(N_H) for the cubic negative formula NHN_H. The Lean~4 development formalizes the formula THT_H for every degree and every degree sequence, its score decomposition, repair and optimum identity, the arithmetic transfers, the MAX-CUT clause count and lifting step, and the hard-score optima 4m+α4m+\alpha and m+αm+\alpha; the Goemans--Williamson, Berman--Fujito and Unique Games statements are explicit hypotheses taken from the literature.

Author comments: This submission is supported by a Lean 4 formalization, available at https://github.com/frankvegadelgado/paloma. The formalization covers the exact optimum identities, the repair and lifting steps, and the arithmetic of the approximation ratios. The Goemans–Williamson, Berman–Fujito and Trevisan guarantees are taken from the literature and are stated as explicit hypotheses; the Unique Games thresholds are cited in the paper and are not formalized. The formalization will be submitted to Palomar, and its acceptance is not guaranteed.

References

  1. P. Alimonti and V. Kann, Some APX-completeness results for cubic graphs , Theoretical Computer Science 237 (2000), 123--134. https://doi.org/10.1016/S0304-3975(98)00158-3.DOI
  2. R. M. Karp, Reducibility among combinatorial problems , in Complexity of Computer Computations, Plenum, 1972, 85--103.
  3. J. Håstad, Clique is hard to approximate within n1−ϵn^{1-\epsilon} , Acta Mathematica 182 (1999), 105--142.
  4. D. Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number , Theory of Computing 3 (2007), 103--128.
  5. S. Khot, On the power of unique 2-prover 1-round games , STOC 2002, 767--775.
  6. S. Khot and O. Regev, Vertex cover might be hard to approximate to within 2−ϵ2-\epsilon , Journal of Computer and System Sciences 74 (2008), 335--349.
  7. P. Austrin, S. Khot and M. Safra, Inapproximability of vertex cover and independent set in bounded degree graphs , Theory of Computing 7 (2011), 27--43.
  8. S. O. Chan, Approximation resistance from pairwise-independent subgroups , Journal of the ACM 63 (2016), Article 27. https://doi.org/10.1145/2873054.DOI
  9. E. Halperin, Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs , SIAM Journal on Computing 31 (2002), 1608--1623.
  10. L. Trevisan, Max Cut and the smallest eigenvalue , STOC 2009. https://theory.stanford.edu/~trevisan/pubs/maxcutstoc.pdf.link
Show all 22 referencesShow fewer references
  1. P. Berman and T. Fujito, On approximation properties of the independent set problem for low degree graphs , Theory of Computing Systems 32 (1999), 115--132. https://doi.org/10.1007/s002240000113.DOI
  2. J. Brakensiek, N. Huang, and U. Zwick, Tight approximability of MAX 2-SAT and relatives, under UGC , Proceedings of SODA 2024, 1328--1344. https://doi.org/10.1137/1.9781611977912.53.DOI
  3. U. Feige, M. Karpinski, and M. Langberg, Improved approximation of Max-Cut on graphs of bounded degree , Journal of Algorithms 43 (2002), 201--219.
  4. E. Halperin, D. Livnat, and U. Zwick, MAX CUT in cubic graphs , Journal of Algorithms 53 (2004), 169--185. https://doi.org/10.1016/j.jalgor.2004.06.001.DOI
  5. J.-T. Hsieh and P. K. Kothari, Approximating Max-Cut on bounded degree graphs: tighter analysis of the FKL algorithm , ICALP 2023, arXiv:2206.09204. https://arxiv.org/abs/2206.09204.arXiv
  6. S. Ghoshal, N. Huang, E. Lee, K. Makarychev, and Y. Makarychev, Threshold rounding and bounded-degree Boolean MAX 2-CSP , arXiv:2607.11050, 2026. https://arxiv.org/abs/2607.11050.arXiv
  7. M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming , Journal of the ACM 42 (1995), 1115--1145.
  8. S. Khot, G. Kindler, E. Mossel, and R. O'Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? , SIAM Journal on Computing 37 (2007), 319--357.
  9. S. Mahajan and H. Ramesh, Derandomizing approximation algorithms based on semidefinite programming , SIAM Journal on Computing 28 (1999), 1641--1663.
  10. OpenAI, Proof of Khot's Unique Games Conjecture (entry 102 of the OpenAI mathematics release, 6 October 2026), GitHub repository openai/math ; not peer reviewed. https://github.com/openai/math.link
  11. V. Raman, B. Ravikumar, and S. Srinivasa Rao, A simplified NP-complete MAXSAT problem , Information Processing Letters 65 (1998), 1--6.
  12. F. Vega, Paloma: MAX-HORN-2SAT and MAX-CUT formalization , GitHub, 2026. https://github.com/frankvegadelgado/paloma.link

Version history

  1. v1 · 16 pagesSubmitted by Frank VegaThis submission is supported by a Lean 4 formalization, available at https://github.com/frankvegadelgado/paloma. The formalization covers the exact optimum identities, the repair and lifting steps, and the arithmetic of the approximation ratios. The Goemans–Williamson, Berman–Fujito and Trevisan guarantees are taken from the literature and are stated as explicit hypotheses; the Unique Games thresholds are cited in the paper and are not formalized. The formalization will be submitted to Palomar, and its acceptance is not guaranteed.CurrentNov 21, 2026