HEXAGONbeta

An Approximate Solution to the Minimum Vertex Cover Problem: The Salvador Algorithm

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

Contributed by Frank Vega ↗

Version 1 / Oct 18, 2026 / CC BY 4.0

Abstract

Minimum Vertex Cover has a classical linear-time ratio of 22, and under the Unique Games Conjecture no polynomial-time algorithm achieves a fixed ratio below 22 unless P=NP\mathrm{P}=\mathrm{NP}. We present version 0.1.4 of \textsc{Salvador}, a linear-time ensemble of seventeen strategies, numbered in the order in which they are computed: twelve base strategies (component amplification before a maximal matching, the maximal matching itself, degree and weight heuristics, reductions to auxiliary problems that are solved exactly, a decomposition into bipartite layers, a weighted subdivision reduction and a bounded-treewidth dynamic program), followed by five improvers (a union pass, local search, reduce-and-search, consensus forcing and a swap-maximize refinement). We prove that every strategy runs in O((n+m) α(n))O((n+m)\,\alpha(n)) time, and that the returned cover has at most 2τ−r2\tau-r vertices, where rr is the number of components with an edge, so the ratio is at most 1.9999999991.999999999 whenever τ≤109r\tau\le10^{9}r. We prove exactness or a bounded ratio on several classes of graphs, among them every bipartite graph on which the Hopcroft--Karp phases of the layer strategy reach a maximum matching, and we give a per-instance certificate: a cover with at most 2L−∣M∣2L-|M| vertices, for a lower bound L≤τL\le\tau and the maximal matching MM, is within ratio 3/23/2 on that instance. In a reproducible suite the returned cover satisfies ∣C∣≤2τ−∣M∣|C|\le2\tau-|M| on all 291291 tested graphs with a known optimum and is certified on the six without one, although single strategies violate it; on the 6868 DIMACS clique complements it is never worse than Hvala and optimal on 3737 instances against 1818. Whether ∣C∣≤2τ−∣M∣|C|\le2\tau-|M| holds on every graph is stated as a conjecture: a proof would give a linear-time 3/23/2-approximation and would refute the Unique Games Conjecture unless P=NP\mathrm{P}=\mathrm{NP}.

Provenance statement

The author designed the strategies of Salvador, 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.

References

  1. Karp, Richard M. Reducibility Among Combinatorial Problems. 50 Years of Integer Programming 1958–2008: From the Early Years to the State-of-the-Art, pp. 219–241. 2010DOI
  2. Papadimitriou, Christos H.; Steiglitz, Kenneth. Combinatorial Optimization: Algorithms and Complexity. Courier Corporation. 1998
  3. Karakostas, George. A Better Approximation Ratio for the Vertex Cover Problem. ACM Transactions on Algorithms, vol. 5, no. 4, pp. 1–8. 2009DOI
  4. Karpinski, Marek; Zelikovsky, Alexander. Approximating Dense Cases of Covering Problems. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26, pp. 147–164. 1996
  5. Dinur, Irit; Safra, Samuel. On the Hardness of Approximating Minimum Vertex Cover. Annals of Mathematics, vol. 162, pp. 439–485. 2005DOI
  6. Khot, Subhash; Minzer, Dor; Safra, Muli. Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science, pp. 592–601. 2018DOI
  7. 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
  8. 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
  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. 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
Show all 37 referencesShow fewer references
  1. Bonnet, Édouard; Rzążewski, Paweł. An 11/611/6-Approximation Algorithm for Vertex Cover on String Graphs. 41st International Symposium on Computational Geometry (SoCG 2025), vol. 332, pp. 24:1–24:15. 2025DOI
  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. Salvador: Approximate Vertex Cover Solver. 2026. Python package version 0.1.4. https://pypi.org/project/salvadorlink
  4. Vega, Frank. An Approximate Solution to the Minimum Vertex Cover Problem: The Hvala Algorithm. Gauge Freedom Journal, vol. 1, no. 1. 2026DOI
  5. Vega, Frank. Hvala: Approximate Vertex Cover Solver. 2026. https://pypi.org/project/hvalalink
  6. Vega, Frank. An approximate solution to the minimum vertex cover problem: the Hallelujah algorithm. International Journal of Parallel, Emergent and Distributed Systems. 2026. , published online 9 May 2026DOI
  7. Bar-Yehuda, Reuven; Even, Shimon. A local-ratio theorem for approximating the weighted vertex cover problem. Analysis and Design of Algorithms for Combinatorial Problems, vol. 25, pp. 27–46. 1985. http://www.cs.technion.ac.il/~reuven/PDF/vc_lr.pdflink
  8. Baker, Brenda S. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, vol. 41, no. 1, pp. 153–180. 1994DOI
  9. Hopcroft, John E.; Karp, Richard M. An n5/2n^{5/2} Algorithm for Maximum Matchings in Bipartite Graphs. SIAM Journal on Computing, vol. 2, no. 4, pp. 225–231. 1973DOI
  10. Konig, Denes. Graphen und Matrizen. Matematikai es Fizikai Lapok, vol. 38, pp. 116–119. 1931
  11. Yannakakis, Mihalis; Gavril, Fanica. Edge Dominating Sets in Graphs. SIAM Journal on Applied Mathematics, vol. 38, no. 3, pp. 364–372. 1980DOI
  12. Chen, Jianer; Kanj, Iyad A.; Jia, Weijia. Vertex Cover: Further Observations and Further Improvements. Journal of Algorithms, vol. 41, no. 2, pp. 280–301. 2001DOI
  13. Chang, Lijun; Li, Wei; Zhang, Wenjie. Computing a Near-Maximum Independent Set in Linear Time by Reducing-Peeling. Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD), pp. 1181–1196. 2017DOI
  14. 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
  15. Karp, Richard M.; Sipser, Michael. Maximum matchings in sparse random graphs. Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, pp. 364–375. 1981DOI
  16. Caro, Yair. New Results on the Independence Number. 1979
  17. Wei, Victor K. A Lower Bound on the Stability Number of a Simple Graph. no. 81-11217-9. 1981
  18. Hall, Philip. On Representatives of Subsets. Journal of the London Mathematical Society, vol. s1-10, no. 1, pp. 26–30. 1935DOI
  19. Hoffman, Alan J. On eigenvalues and colorings of graphs. Graph Theory and its Applications, pp. 79–91. 1970
  20. Johnson, David S. Approximation Algorithms for Combinatorial Problems. Journal of Computer and System Sciences, vol. 9, no. 3, pp. 256–278. 1974DOI
  21. Alimonti, Paola; Kann, Viggo. Some APX-completeness Results for Cubic Graphs. Theoretical Computer Science, vol. 237, no. 1–2, pp. 123–134. 2000DOI
  22. Tarjan, Robert Endre. Efficiency of a good but not linear set union algorithm. Journal of the ACM, vol. 22, no. 2, pp. 215–225. 1975DOI
  23. Nemhauser, George L.; Trotter, Leslie E. Vertex Packings: Structural Properties and Algorithms. Mathematical Programming, vol. 8, no. 1, pp. 232–248. 1975DOI
  24. Friedman, Joel. A Proof of Alon's Second Eigenvalue Conjecture and Related Problems. American Mathematical Society, vol. 195, no. 910. 2008DOI
  25. Frieze, Alan M.; Łuczak, Tomasz. On the Independence and Chromatic Numbers of Random Regular Graphs. Journal of Combinatorial Theory, Series B, vol. 54, no. 1, pp. 123–132. 1992DOI
  26. Nguyen, ThanhVu; Bui, Thang. NP-Complete Benchmark Instances. 2025. Vertex cover DIMACS clique complements. https://roars.dev/npbench/link
  27. Mascia, Franco. The Maximum Clique Problem – DIMACS Benchmark Set. 2015. Compiled clique-number values for DIMACS Second Implementation Challenge instances. https://iridia.ulb.ac.be/~fmascia/maximum_clique/DIMACS-benchmarklink

Version history

  1. v1Submitted by Frank VegaInitial depositCurrentOct 18, 2026