An Approximate Solution to the Minimum Vertex Cover Problem: The Salvador Algorithm
Version 2 / Oct 18, 2026 / CC BY 4.0
Abstract
Minimum Vertex Cover has a classical linear-time ratio of , and under the Unique Games Conjecture no polynomial-time algorithm achieves a fixed ratio below unless . We present version 0.1.6 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 time, and that the returned cover has at most vertices, where is the number of components with an edge, so the ratio is at most whenever . 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 vertices, for a lower bound and the maximal matching , is within ratio on that instance. In a reproducible suite the returned cover satisfies on all tested graphs with a known optimum and is certified on the six without one, although single strategies violate it; on the DIMACS clique complements it is never worse than Hvala and optimal on instances against . Whether holds on every graph is stated as a conjecture: a proof would give a linear-time -approximation and would refute the Unique Games Conjecture unless .
Provenance statement
Tools used
- Anthropic
- Claude OpusVersion 5.5
- Anthropic
- Claude FableVersion 5.2
References
- 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
- Papadimitriou, Christos H.; Steiglitz, Kenneth. Combinatorial Optimization: Algorithms and Complexity. Courier Corporation. 1998
- Karakostas, George. A Better Approximation Ratio for the Vertex Cover Problem. ACM Transactions on Algorithms, vol. 5, no. 4, pp. 1–8. 2009DOI
- 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
- Dinur, Irit; Safra, Samuel. On the Hardness of Approximating Minimum Vertex Cover. Annals of Mathematics, vol. 162, pp. 439–485. 2005DOI
- 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
- 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
- Khot, Subhash; Regev, Oded. Vertex Cover Might Be Hard to Approximate to Within . Journal of Computer and System Sciences, vol. 74, no. 3, pp. 335–349. 2008DOI
- 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
- 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 38 referencesShow fewer references
- Bonnet, Édouard; Rzążewski, Paweł. An -Approximation Algorithm for Vertex Cover on String Graphs. 41st International Symposium on Computational Geometry (SoCG 2025), vol. 332, pp. 24:1–24:15. 2025DOI
- 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
- Vega, Frank. Salvador: Approximate Vertex Cover Solver. 2026. Python package version 0.1.4. https://pypi.org/project/salvadorlink
- Vega, Frank. An Approximate Solution to the Minimum Vertex Cover Problem: The Hvala Algorithm. Gauge Freedom Journal, vol. 1, no. 1. 2026DOI
- Vega, Frank. Hvala: Approximate Vertex Cover Solver. 2026. https://pypi.org/project/hvalalink
- 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
- 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
- Baker, Brenda S. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, vol. 41, no. 1, pp. 153–180. 1994DOI
- Hopcroft, John E.; Karp, Richard M. An Algorithm for Maximum Matchings in Bipartite Graphs. SIAM Journal on Computing, vol. 2, no. 4, pp. 225–231. 1973DOI
- Konig, Denes. Graphen und Matrizen. Matematikai es Fizikai Lapok, vol. 38, pp. 116–119. 1931
- Yannakakis, Mihalis; Gavril, Fanica. Edge Dominating Sets in Graphs. SIAM Journal on Applied Mathematics, vol. 38, no. 3, pp. 364–372. 1980DOI
- 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
- 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
- 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
- Cai, Shaowei; Su, Kaile; Luo, Chuan; Sattar, Abdul. NuMVC: An efficient local search algorithm for minimum vertex cover. Journal of Artificial Intelligence Research, vol. 46, pp. 687–716. 2013DOI
- 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
- Caro, Yair. New Results on the Independence Number. 1979
- Wei, Victor K. A Lower Bound on the Stability Number of a Simple Graph. no. 81-11217-9. 1981
- Hall, Philip. On Representatives of Subsets. Journal of the London Mathematical Society, vol. s1-10, no. 1, pp. 26–30. 1935DOI
- Hoffman, Alan J. On eigenvalues and colorings of graphs. Graph Theory and its Applications, pp. 79–91. 1970
- Johnson, David S. Approximation Algorithms for Combinatorial Problems. Journal of Computer and System Sciences, vol. 9, no. 3, pp. 256–278. 1974DOI
- Alimonti, Paola; Kann, Viggo. Some APX-completeness Results for Cubic Graphs. Theoretical Computer Science, vol. 237, no. 1–2, pp. 123–134. 2000DOI
- 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
- Nemhauser, George L.; Trotter, Leslie E. Vertex Packings: Structural Properties and Algorithms. Mathematical Programming, vol. 8, no. 1, pp. 232–248. 1975DOI
- Friedman, Joel. A Proof of Alon's Second Eigenvalue Conjecture and Related Problems. American Mathematical Society, vol. 195, no. 910. 2008DOI
- 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
- Nguyen, ThanhVu; Bui, Thang. NP-Complete Benchmark Instances. 2025. Vertex cover DIMACS clique complements. https://roars.dev/npbench/link
- 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
- v1 · 31 pagesSubmitted by Frank VegaInitial depositSupersededOct 18, 2026
- v2 · 32 pagesSubmitted by Frank VegaThe quadratic step in c9 was in `bipartite_layers_cover`: it re-filtered the entire vertex order once per connected component, costing O(components × n). Because c9 rarely has many components on the original graph, this cost never surfaced. The running time is now guaranteed to be linear.CurrentNov 17, 2026