HEXAGONbeta

The Esperanza Algorithm for Maximum Independent Set

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

Contributed by Frank Vega ↗

Version 1 / Nov 02, 2026 / CC BY 4.0

Abstract

The maximum independent set problem asks for the largest set of pairwise non-adjacent vertices in an undirected graph. It is NP-hard to approximate within n1−εn^{1-\varepsilon} for every ε>0\varepsilon>0, and under the Unique Games Conjecture it is hard to approximate within O(Δ/log⁡2Δ)O(\Delta/\log^2\Delta) on graphs of maximum degree Δ\Delta; the Khot--Regev form of the conjecture, for which a proof has been reported but not yet peer reviewed, also rules out a (2−ε)(2-\varepsilon)-approximation of Minimum Vertex Cover. We present version 0.1.6 of \textsc{Esperanza}, which takes the better of a dynamic minimum-degree (Caro--Wei) greedy set and the complement of the \textsc{Salvador} vertex cover, and improves it by three budgeted local searches: repair-and-grow restarts at the cover vertices and at a maximum-degree vertex, chained local restarts realising (k,k+1)(k,k+1)-improvements, and an iterated (1,2)(1,2)-swap search. We prove that it runs in O((n+m) αA(n))O((n+m)\,\alpha_{\mathrm A}(n)) expected time for fixed budgets, with αA\alpha_{\mathrm A} the inverse Ackermann function. We prove that the output is a maximal independent set, that its complementary vertex cover has at most 2τ−r2\tau-r vertices, where τ\tau is the minimum cover size and rr the number of components with an edge, and that the ratio is at most (Δ+2)/3(\Delta+2)/3 on graphs of maximum degree Δ\Delta. We prove the ratio 2n2\sqrt n on every graph with Δ≤n\Delta\le\sqrt n and on three further classes, and state it for all graphs as a conjecture, whose proof would imply P=NP\mathrm{P}=\mathrm{NP}. We also state the conjecture that the complementary cover has at most 2τ−∣M∣2\tau-|M| vertices for the NetworkX minimum maximal matching MM; a proof would give a 3/23/2-approximation for Minimum Vertex Cover and refute the Unique Games Conjecture unless P=NP\mathrm{P}=\mathrm{NP}. In reproducible experiments the returned set is optimal on all 30 00030\,000 graphs of a suite certified by an exact integer program; on 4040 Khot--Regev YES instances with 640640 to 2 5602\,560 vertices the conjectured bound is certified on 3838 and open on 22; and on 3131 bounded-degree graphs the certified ratio is at most 1.07691.0769 on the families with a planted independent set.

Provenance statement

The author designed the strategies of Esperanza, and used Claude Opus 5.5 to implement them by vibe coding and to improve the readability of this manuscript. After using this tool, the author reviewed and edited the code and the content as needed and takes full responsibility for the content of the publication.

Tools used

Anthropic
Claude OpusVersion 5.5

References

  1. Karp, Richard M. Reducibility among Combinatorial Problems. Complexity of Computer Computations, pp. 85–103. 1972DOI
  2. Håstad, Johan. Clique is hard to approximate within n1−ϵn^{1-\epsilon}. Acta Mathematica, vol. 182, no. 1, pp. 105–142. 1999DOI
  3. Zuckerman, David. Linear degree extractors and the inapproximability of Max Clique and Chromatic Number. Theory of Computing, vol. 3, no. 6, pp. 103–128. 2007DOI
  4. Boppana, Ravi; Halldórsson, Magnús M. Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, vol. 32, no. 2, pp. 180–196. 1992DOI
  5. Feige, Uriel. Approximating maximum clique by removing subgraphs. SIAM Journal on Discrete Mathematics, vol. 18, no. 2, pp. 219–225. 2004DOI
  6. Halldórsson, Magnús M.; Radhakrishnan, Jaikumar. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica, vol. 18, no. 1, pp. 145–163. 1997DOI
  7. Halperin, Eran. Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs. SIAM Journal on Computing, vol. 31, no. 5, pp. 1608–1623. 2002DOI
  8. Khot, Subhash. On the Power of Unique 2-Prover 1-Round Games. Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 767–775. 2002DOI
  9. Austrin, Per; Khot, Subhash; Safra, Muli. Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. Theory of Computing, vol. 7, no. 3, pp. 27–43. 2011DOI
  10. Chan, Siu On. Approximation Resistance from Pairwise-Independent Subgroups. Journal of the ACM, vol. 63, no. 3, pp. 27:1–27:32. 2016
Show all 21 referencesShow fewer references
  1. Khot, Subhash; Regev, Oded. Vertex Cover Might Be Hard to Approximate to Within 2−ϵ2-\epsilon. Journal of Computer and System Sciences, vol. 74, no. 3, pp. 335–349. 2008DOI
  2. OpenAI Math Team. The Unique Games Conjecture and Optimal Approximation Thresholds (Result Family 102). 2026. Manuscripts and Lean artifacts available at https://github.com/openai/math/blob/main/lean/docs/102.md. GitHub Repositorylink
  3. Vega, Frank. Esperanza: Approximate Independent Set Solver. 2026. Python package version 0.1.6. https://pypi.org/project/esperanzalink
  4. Caro, Yair. New results on the independence number. 1979
  5. Wei, Victor K. A lower bound on the stability number of a simple graph. no. Technical Memorandum 81-11217-9. 1981
  6. Vega, Frank. An Approximate Solution to the Minimum Vertex Cover Problem: The Salvador Algorithm. 2026. Manuscript; preprint at https://www.preprints.org/manuscript/202605.2000link
  7. Vega, Frank. Salvador: Approximate Vertex Cover Solver. 2026. Python package version 0.1.4. https://pypi.org/project/salvadorlink
  8. Andrade, Diogo V.; Resende, Mauricio G. C.; Werneck, Renato F. Fast local search for the maximum independent set problem. Journal of Heuristics, vol. 18, no. 4, pp. 525–547. 2012DOI
  9. Hagberg, Aric A.; Schult, Daniel A.; Swart, Pieter J. Exploring network structure, dynamics, and function using NetworkX. Proceedings of the 7th Python in Science Conference (SciPy 2008), pp. 11–15. 2008
  10. Virtanen, Pauli; Gommers, Ralf; Oliphant, Travis E.; others. SciPy 1.0: Fundamental algorithms for scientific computing in Python. Nature Methods, vol. 17, pp. 261–272. 2020DOI
  11. Huangfu, Qi; Hall, J. A. Julian. Parallelizing the dual revised simplex method. Mathematical Programming Computation, vol. 10, no. 1, pp. 119–142. 2018DOI

Version history

  1. v1Submitted by Frank VegaInitial depositCurrentOct 31, 2026