@incollection{karp2009reducibility,
  title = {Reducibility {A}mong {C}ombinatorial {P}roblems},
  author = {Karp, Richard M.},
  booktitle = {50 Years of Integer Programming 1958--2008: From the Early Years to the State-of-the-Art},
  pages = {219--241},
  year = {2010},
  publisher = {Springer},
  address = {Berlin, Germany},
  doi = {10.1007/978-3-540-68279-0_8}
}

@book{papadimitriou1998combinatorial,
  title = {Combinatorial {O}ptimization: {A}lgorithms and {C}omplexity},
  author = {Papadimitriou, Christos H. and Steiglitz, Kenneth},
  year = {1998},
  publisher = {Courier Corporation},
  address = {North Chelmsford (MA)}
}

@article{karakostas2009better,
  title = {A {B}etter {A}pproximation {R}atio for the {V}ertex {C}over {P}roblem},
  author = {Karakostas, George},
  journal = {ACM Transactions on Algorithms},
  volume = {5},
  number = {4},
  pages = {1--8},
  year = {2009},
  doi = {10.1145/1597036.1597045}
}

@inproceedings{karpinski1996approximating,
  title = {Approximating {D}ense {C}ases of {C}overing {P}roblems},
  author = {Karpinski, Marek and Zelikovsky, Alexander},
  booktitle = {DIMACS Series in Discrete Mathematics and Theoretical Computer Science},
  volume = {26},
  pages = {147--164},
  year = {1996},
  address = {Providence, Rhode Island}
}

@article{dinur2005hardness,
  title = {On the {H}ardness of {A}pproximating {M}inimum {V}ertex {C}over},
  author = {Dinur, Irit and Safra, Samuel},
  journal = {Annals of Mathematics},
  volume = {162},
  pages = {439--485},
  year = {2005},
  doi = {10.4007/annals.2005.162.439}
}

@inproceedings{khot2017independent,
  title = {On {I}ndependent {S}ets, 2-to-2 {G}ames, and {G}rassmann {G}raphs},
  author = {Khot, Subhash and Minzer, Dor and Safra, Muli},
  booktitle = {Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing},
  pages = {576--589},
  year = {2017},
  doi = {10.1145/3055399.3055432},
  publisher={Association for Computing Machinery},
  address = {Montreal, Qu\'ebec, Canada}
}

@inproceedings{dinur2018towards,
  author = {Dinur, Irit and Khot, Subhash and Kindler, Guy and Minzer, Dor and Safra, Muli},
  title = {Towards a proof of the 2-to-1 games conjecture?},
  booktitle = {Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing},
  pages = {376--389},
  year = {2018},
  address = {Los Angeles, California},
  doi = {10.1145/3188745.3188804}
}

@inproceedings{khot2018pseudorandom,
  author = {Khot, Subhash and Minzer, Dor and Safra, Muli},
  title = {Pseudorandom {S}ets in {G}rassmann {G}raph {H}ave {N}ear-{P}erfect {E}xpansion},
  booktitle = {2018 IEEE 59th Annual Symposium on Foundations of Computer Science},
  pages = {592--601},
  year = {2018},
  address = {Paris, France},
  doi = {10.1109/FOCS.2018.00062}
}

@article{khot2008vertex,
  title = {Vertex {C}over {M}ight {B}e {H}ard to {A}pproximate to {W}ithin $2-\epsilon$},
  author = {Khot, Subhash and Regev, Oded},
  journal = {Journal of Computer and System Sciences},
  volume = {74},
  number = {3},
  pages = {335--349},
  year = {2008},
  doi = {10.1016/j.jcss.2007.06.019}
}

@inproceedings{khot2002unique,
  title = {On the {P}ower of {U}nique 2-{P}rover 1-{R}ound {G}ames},
  author = {Khot, Subhash},
  booktitle = {Proceedings of the 34th Annual ACM Symposium on Theory of Computing},
  pages = {767--775},
  year = {2002},
  doi = {10.1145/509907.510017},
  publisher={Association for Computing Machinery},
  address = {Montreal, Qu\'ebec, Canada}
}

@article{baker1994approximation,
  title   = {Approximation algorithms for {NP}-complete problems on planar graphs},
  author  = {Baker, Brenda S.},
  journal = {Journal of the ACM},
  volume  = {41},
  number  = {1},
  pages   = {153--180},
  year    = {1994},
  doi     = {10.1145/174644.174650}
}

@article{tarjan1975efficiency,
  title   = {Efficiency of a good but not linear set union algorithm},
  author  = {Tarjan, Robert Endre},
  journal = {Journal of the ACM},
  volume  = {22},
  number  = {2},
  pages   = {215--225},
  year    = {1975},
  doi     = {10.1145/321879.321884}
}

@book{johnson1996cliques,
  author    = {David S. Johnson and Michael A. Trick},
  title     = {Cliques, {C}oloring, and {S}atisfiability: {S}econd {DIMACS} {I}mplementation {C}hallenge},
  series    = {DIMACS Series in Discrete Mathematics and Theoretical Computer Science},
  volume    = {26},
  publisher = {American Mathematical Society},
  address   = {Boston, MA, USA},
  year      = {1996}
}

@misc{DIMACSClique,
  title        = {The {M}aximum {C}lique {P}roblem -- {DIMACS} {B}enchmark {S}et},
  author       = {Mascia, Franco},
  year         = {2015},
  howpublished = {\url{https://iridia.ulb.ac.be/~fmascia/maximum_clique/DIMACS-benchmark}},
  note         = {Compiled clique-number values for DIMACS Second Implementation Challenge instances}
}

@misc{NPBench,
  title        = {{NP}-{C}omplete {B}enchmark {I}nstances},
  author       = {Nguyen, ThanhVu and Bui, Thang},
  howpublished = {\url{https://roars.dev/npbench/}},
  year         = {2025},
  note         = {Vertex cover DIMACS clique complements}
}

@incollection{barYehudaEven1985,
  title     = {A local-ratio theorem for approximating the weighted vertex cover problem},
  author    = {Bar-Yehuda, Reuven and Even, Shimon},
  booktitle = {Analysis and Design of Algorithms for Combinatorial Problems},
  series    = {Annals of Discrete Mathematics},
  volume    = {25},
  pages     = {27--46},
  year      = {1985},
  publisher = {Elsevier},
  note      = {\url{http://www.cs.technion.ac.il/~reuven/PDF/vc_lr.pdf}}
}

@article{konig1931graphen,
  title   = {Graphen und {M}atrizen},
  author  = {Konig, Denes},
  journal = {Matematikai es Fizikai Lapok},
  volume  = {38},
  pages   = {116--119},
  year    = {1931}
}

@misc{Vega26Salvador,
  title        = {Salvador: {A}pproximate {V}ertex {C}over {S}olver},
  author       = {Vega, Frank},
  year         = {2026},
  note         = {Python package version 0.1.4},
  howpublished = {\url{https://pypi.org/project/salvador}}
}

@article{Vega26Hvala,
  author    = {Vega, Frank},
  title     = {An {A}pproximate {S}olution to the {M}inimum {V}ertex {C}over {P}roblem: The {Hvala} {A}lgorithm},
  journal   = {Gauge Freedom Journal},
  year      = {2026},
  volume    = {1},
  number    = {1},
  eid       = {004},
  publisher = {Gauge Freedom},
  doi       = {10.65323/gfj.2026.004},
  url       = {https://www.gaugefreedom.org/article/v1-i1-004-the-hvala-algorithm/}
}

@misc{Vega26HvalaPyPI,
  title        = {Hvala: {A}pproximate {V}ertex {C}over {S}olver},
  author       = {Vega, Frank},
  year         = {2026},
  howpublished = {\url{https://pypi.org/project/hvala}}
}

@article{andrade2012fast,
  author  = {Andrade, Diogo V. and Resende, Mauricio G. C. and Werneck, Renato F.},
  title   = {Fast local search for the maximum independent set problem},
  journal = {Journal of Heuristics},
  volume  = {18},
  number  = {4},
  pages   = {525--547},
  year    = {2012},
  doi     = {10.1007/s10732-012-9196-4}
}

@inproceedings{karp1981maximum,
  author    = {Karp, Richard M. and Sipser, Michael},
  title     = {Maximum matchings in sparse random graphs},
  booktitle = {Proceedings of the 22nd Annual Symposium on Foundations of Computer Science},
  pages     = {364--375},
  year      = {1981},
  doi       = {10.1109/SFCS.1981.21}
}

@incollection{hoffman1970eigenvalues,
  author    = {Hoffman, Alan J.},
  title     = {On eigenvalues and colorings of graphs},
  booktitle = {Graph Theory and its Applications},
  editor    = {Harris, Bernard},
  publisher = {Academic Press},
  address   = {New York},
  pages     = {79--91},
  year      = {1970}
}

@article{hopcroft1973algorithm,
  title   = {An {$n^{5/2}$} Algorithm for Maximum Matchings in Bipartite Graphs},
  author  = {Hopcroft, John E. and Karp, Richard M.},
  journal = {SIAM Journal on Computing},
  volume  = {2},
  number  = {4},
  pages   = {225--231},
  year    = {1973},
  doi     = {10.1137/0202019}
}

@misc{openai2026ugc,
  author       = {{OpenAI Math Team}},
  title        = {The {U}nique {G}ames {C}onjecture and {O}ptimal {A}pproximation {T}hresholds ({R}esult {F}amily 102)},
  howpublished = {GitHub Repository},
  year         = {2026},
  month        = oct,
  note         = {Manuscripts and Lean artifacts available at \url{https://github.com/openai/math/blob/main/lean/docs/102.md}},
  url          = {https://github.com/openai/math}
}

@article{austrin2011inapproximability,
  title = {Inapproximability of {V}ertex {C}over and {I}ndependent {S}et in {B}ounded {D}egree {G}raphs},
  author = {Austrin, Per and Khot, Subhash and Safra, Muli},
  journal = {Theory of Computing},
  volume = {7},
  number = {3},
  pages = {27--43},
  year = {2011},
  doi = {10.4086/toc.2011.v007a003}
}

@article{halperin2002improved,
  title = {Improved {A}pproximation {A}lgorithms for the {V}ertex {C}over {P}roblem in {G}raphs and {H}ypergraphs},
  author = {Halperin, Eran},
  journal = {SIAM Journal on Computing},
  volume = {31},
  number = {5},
  pages = {1608--1623},
  year = {2002},
  doi = {10.1137/S0097539700381097}
}

@article{johnson1974approximation,
  title = {Approximation {A}lgorithms for {C}ombinatorial {P}roblems},
  author = {Johnson, David S.},
  journal = {Journal of Computer and System Sciences},
  volume = {9},
  number = {3},
  pages = {256--278},
  year = {1974},
  doi = {10.1016/S0022-0000(74)80044-9}
}

@article{alimonti2000some,
  title = {Some {APX}-completeness {R}esults for {C}ubic {G}raphs},
  author = {Alimonti, Paola and Kann, Viggo},
  journal = {Theoretical Computer Science},
  volume = {237},
  number = {1--2},
  pages = {123--134},
  year = {2000},
  doi = {10.1016/S0304-3975(98)00158-3}
}

@article{vega2026hallelujah,
  title = {An approximate solution to the minimum vertex cover problem: the {H}allelujah algorithm},
  author = {Vega, Frank},
  journal = {International Journal of Parallel, Emergent and Distributed Systems},
  year = {2026},
  note = {, published online 9 May 2026},
  doi = {10.1080/17445760.2026.2660724}
}

@article{yannakakis1980edge,
  title = {Edge {D}ominating {S}ets in {G}raphs},
  author = {Yannakakis, Mihalis and Gavril, Fanica},
  journal = {SIAM Journal on Applied Mathematics},
  volume = {38},
  number = {3},
  pages = {364--372},
  year = {1980},
  doi = {10.1137/0138030}
}

@techreport{caro1979new,
  author      = {Caro, Yair},
  title       = {New {R}esults on the {I}ndependence {N}umber},
  institution = {Tel Aviv University},
  type        = {Technical Report},
  year        = {1979}
}

@techreport{wei1981lower,
  author      = {Wei, Victor K.},
  title       = {A {L}ower {B}ound on the {S}tability {N}umber of a {S}imple {G}raph},
  institution = {Bell Laboratories},
  type        = {Technical Memorandum},
  number      = {81-11217-9},
  year        = {1981}
}

@article{nemhauser1975vertex,
  author  = {Nemhauser, George L. and Trotter, Leslie E.},
  title   = {Vertex {P}ackings: {S}tructural {P}roperties and {A}lgorithms},
  journal = {Mathematical Programming},
  volume  = {8},
  number  = {1},
  pages   = {232--248},
  year    = {1975},
  doi     = {10.1007/BF01580444}
}

@book{friedman2008proof,
  author    = {Friedman, Joel},
  title     = {A {P}roof of {A}lon's {S}econd {E}igenvalue {C}onjecture and {R}elated {P}roblems},
  series    = {Memoirs of the American Mathematical Society},
  volume    = {195},
  number    = {910},
  publisher = {American Mathematical Society},
  address   = {Providence, RI},
  year      = {2008},
  doi       = {10.1090/memo/0910}
}

@article{frieze1992independence,
  author  = {Frieze, Alan M. and {\L}uczak, Tomasz},
  title   = {On the {I}ndependence and {C}hromatic {N}umbers of {R}andom {R}egular {G}raphs},
  journal = {Journal of Combinatorial Theory, Series B},
  volume  = {54},
  number  = {1},
  pages   = {123--132},
  year    = {1992},
  doi     = {10.1016/0095-8956(92)90070-E}
}

@article{hall1935representatives,
  author  = {Hall, Philip},
  title   = {On {R}epresentatives of {S}ubsets},
  journal = {Journal of the London Mathematical Society},
  volume  = {s1-10},
  number  = {1},
  pages   = {26--30},
  year    = {1935},
  doi     = {10.1112/jlms/s1-10.37.26}
}

@inproceedings{chang2017computing,
  author    = {Chang, Lijun and Li, Wei and Zhang, Wenjie},
  title     = {Computing a Near-Maximum Independent Set in Linear Time by Reducing-Peeling},
  booktitle = {Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD)},
  pages     = {1181--1196},
  year      = {2017},
  doi       = {10.1145/3035918.3035939}
}

@article{chen2001vertex,
  author  = {Chen, Jianer and Kanj, Iyad A. and Jia, Weijia},
  title   = {Vertex Cover: Further Observations and Further Improvements},
  journal = {Journal of Algorithms},
  volume  = {41},
  number  = {2},
  pages   = {280--301},
  year    = {2001},
  doi     = {10.1006/jagm.2001.1186}
}

@inproceedings{bonnet2025string,
  author    = {Bonnet, {\'E}douard and Rz{\k{a}}{\.{z}}ewski, Pawe{\l}},
  title     = {An $11/6$-Approximation Algorithm for Vertex Cover on String Graphs},
  booktitle = {41st International Symposium on Computational Geometry (SoCG 2025)},
  editor    = {Aichholzer, Oswin and Wang, Haitao},
  series    = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume    = {332},
  pages     = {24:1--24:15},
  year      = {2025},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  doi       = {10.4230/LIPIcs.SoCG.2025.24}
}