@incollection{karp1972reducibility,
  author    = {Karp, Richard M.},
  booktitle = {Complexity of {C}omputer {C}omputations},
  title     = {Reducibility among {C}ombinatorial {P}roblems},
  pages     = {85--103},
  publisher = {Plenum},
  year      = {1972},
  editor    = {Miller, R. E. and Thatcher, J. W. and Bohlinger, J. D.},
  address   = {New York, USA},
  doi       = {10.1007/978-1-4684-2001-2_9}
}

@article{halldorsson1994greedy,
  author    = {Halld{\'o}rsson, Magn{\'u}s M. and Radhakrishnan, Jaikumar},
  title     = {Greed is good: {A}pproximating independent sets in sparse and bounded-degree graphs},
  journal   = {Algorithmica},
  volume    = {18},
  number    = {1},
  pages     = {145--163},
  year      = {1997},
  publisher = {Springer},
  doi       = {10.1007/BF02523693}
}

@article{boppana1992approximating,
  author    = {Boppana, Ravi and Halld{\'o}rsson, Magn{\'u}s M.},
  title     = {Approximating maximum independent sets by excluding subgraphs},
  journal   = {BIT Numerical Mathematics},
  volume    = {32},
  number    = {2},
  pages     = {180--196},
  year      = {1992},
  publisher = {Springer},
  doi       = {10.1007/BF01994876}
}

@article{hastad1999clique,
  author    = {H{\aa}stad, Johan},
  title     = {Clique is hard to approximate within $n^{1-\epsilon}$},
  journal   = {Acta Mathematica},
  volume    = {182},
  number    = {1},
  pages     = {105--142},
  year      = {1999},
  publisher = {Springer},
  doi       = {10.1007/BF02392825}
}

@misc{Vega26,
  author       = {Vega, Frank},
  title        = {Esperanza: {A}pproximate {I}ndependent {S}et {S}olver},
  year         = {2026},
  howpublished = {\url{https://pypi.org/project/esperanza}},
  note         = {Python package version 0.1.6}
}


@techreport{caro1979new,
  author      = {Caro, Yair},
  title       = {New results on the independence number},
  year        = {1979},
  institution = {Tel-Aviv University}
}

@techreport{wei1981lower,
  author      = {Wei, Victor K.},
  title       = {A lower bound on the stability number of a simple graph},
  year        = {1981},
  institution = {Bell Laboratories},
  number      = {Technical Memorandum 81-11217-9}
}

@article{zuckerman2007linear,
  author  = {Zuckerman, David},
  title   = {Linear degree extractors and the inapproximability of {M}ax {C}lique and {C}hromatic {N}umber},
  journal = {Theory of Computing},
  volume  = {3},
  number  = {6},
  pages   = {103--128},
  year    = {2007},
  doi     = {10.4086/toc.2007.v003a006}
}

@article{feige2004approximating,
  author  = {Feige, Uriel},
  title   = {Approximating maximum clique by removing subgraphs},
  journal = {SIAM Journal on Discrete Mathematics},
  volume  = {18},
  number  = {2},
  pages   = {219--225},
  year    = {2004},
  doi     = {10.1137/S089548010240415X}
}

@article{huangfu2018parallelizing,
  author  = {Huangfu, Qi and Hall, J. A. Julian},
  title   = {Parallelizing the dual revised simplex method},
  journal = {Mathematical Programming Computation},
  volume  = {10},
  number  = {1},
  pages   = {119--142},
  year    = {2018},
  doi     = {10.1007/s12532-017-0130-5}
}

@article{virtanen2020scipy,
  author  = {Virtanen, Pauli and Gommers, Ralf and Oliphant, Travis E. and others},
  title   = {{SciPy} 1.0: Fundamental algorithms for scientific computing in {P}ython},
  journal = {Nature Methods},
  volume  = {17},
  pages   = {261--272},
  year    = {2020},
  doi     = {10.1038/s41592-019-0686-2}
}

@inproceedings{hagberg2008exploring,
  author    = {Hagberg, Aric A. and Schult, Daniel A. and Swart, Pieter J.},
  title     = {Exploring network structure, dynamics, and function using {NetworkX}},
  booktitle = {Proceedings of the 7th Python in Science Conference (SciPy 2008)},
  pages     = {11--15},
  year      = {2008},
  address   = {Pasadena, CA, USA}
}

@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{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}
}

@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{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}
}

@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        = {October},
  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}
}

@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}}
}

@unpublished{Vega26SalvadorPaper,
  author = {Vega, Frank},
  title  = {An {A}pproximate {S}olution to the {M}inimum {V}ertex {C}over {P}roblem: {T}he {S}alvador {A}lgorithm},
  year   = {2026},
  note   = {Manuscript; preprint at \url{https://www.preprints.org/manuscript/202605.2000}}
}

@article{chan2016approximation,
  author  = {Chan, Siu On},
  title   = {Approximation {R}esistance from {P}airwise-{I}ndependent {S}ubgroups},
  journal = {Journal of the ACM},
  volume  = {63},
  number  = {3},
  pages   = {27:1--27:32},
  year    = {2016}
}