An approximation for a cubic three-occurrence Horn class
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 the formula satisfies , and every assignment of value is repaired in polynomial time to an independent set of size at least . This gives a polynomial-time approximation from a cubic independent-set approximation and a near-bipartite cut algorithm, an -reduction from cubic MIS, and APX-completeness. For simple -regular graphs the optimum is and the factors are: from the all-true assignment, which is at least for ; from the Berman--Fujito guarantee for and, with a semidefinite cut rounding, for ; and from any -approximate independent set. For arbitrary simple graphs the optimum is .
MAX-CUT on a -regular graph reduces to MAX 2-SAT with the clauses and per edge, of value . The conflict graph is -regular and . A Goemans--Williamson cut gives on the factor for every , and a -dependent analysis gives , where and . For arbitrary simple graphs without isolated vertices the factor exceeds . A cut guarantee on graphs of maximum degree gives , which exceeds in expectation for . A ratio on 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 of three-occurrence Horn formulas obtained from MAX-CUT instances the proved factor exceeds the Unique Games thresholds and 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 , and with edge weights four. The Unique Games thresholds of Brakensiek--Huang--Zwick (), Lewin--Livnat--Zwick () for MAX 2-SAT, and Khot--Kindler--Mossel--O'Donnell () 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 for the cubic negative formula . The Lean~4 development formalizes the formula 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 and ; the Goemans--Williamson, Berman--Fujito and Unique Games statements are explicit hypotheses taken from the literature.
References
- 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
- R. M. Karp, Reducibility among combinatorial problems , in Complexity of Computer Computations, Plenum, 1972, 85--103.
- J. Håstad, Clique is hard to approximate within , Acta Mathematica 182 (1999), 105--142.
- D. Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number , Theory of Computing 3 (2007), 103--128.
- S. Khot, On the power of unique 2-prover 1-round games , STOC 2002, 767--775.
- S. Khot and O. Regev, Vertex cover might be hard to approximate to within , Journal of Computer and System Sciences 74 (2008), 335--349.
- 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.
- S. O. Chan, Approximation resistance from pairwise-independent subgroups , Journal of the ACM 63 (2016), Article 27. https://doi.org/10.1145/2873054.DOI
- E. Halperin, Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs , SIAM Journal on Computing 31 (2002), 1608--1623.
- 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
- 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
- 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
- U. Feige, M. Karpinski, and M. Langberg, Improved approximation of Max-Cut on graphs of bounded degree , Journal of Algorithms 43 (2002), 201--219.
- 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
- 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
- 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
- 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.
- 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.
- S. Mahajan and H. Ramesh, Derandomizing approximation algorithms based on semidefinite programming , SIAM Journal on Computing 28 (1999), 1641--1663.
- 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
- V. Raman, B. Ravikumar, and S. Srinivasa Rao, A simplified NP-complete MAXSAT problem , Information Processing Letters 65 (1998), 1--6.
- F. Vega, Paloma: MAX-HORN-2SAT and MAX-CUT formalization , GitHub, 2026. https://github.com/frankvegadelgado/paloma.link
Version history
- 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