@article{irving1991approximating,
  title     = {On approximating the minimum independent dominating set},
  author    = {Irving, Robert W},
  journal   = {Information Processing Letters},
  volume    = {37},
  number    = {4},
  pages     = {197--200},
  year      = {1991},
  publisher = {Elsevier},
  doi       = {10.1016/0020-0190(91)90188-N}
}

@article{halldorsson1993approximating,
  title     = {Approximating the minimum maximal independence number},
  author    = {Halld{\'o}rsson, Magn{\'u}s M},
  journal   = {Information Processing Letters},
  volume    = {46},
  number    = {4},
  pages     = {169--172},
  year      = {1993},
  publisher = {Elsevier},
  doi       = {10.1016/0020-0190(93)90022-2}
}

@article{chlebik2008approximation,
  title     = {Approximation hardness of dominating set problems in bounded degree graphs},
  author    = {Chleb{\'i}k, Miroslav and Chleb{\'i}kov{\'a}, Janka},
  journal   = {Information and Computation},
  volume    = {206},
  number    = {11},
  pages     = {1264--1275},
  year      = {2008},
  publisher = {Elsevier},
  doi       = {10.1016/j.ic.2008.07.003}
}

@article{loverov2020np,
  title     = {{NP}-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs},
  author    = {Loverov, Ya. A. and Orlovich, Yu. L.},
  journal   = {Journal of Applied and Industrial Mathematics},
  volume    = {14},
  number    = {2},
  pages     = {352--366},
  year      = {2020},
  publisher = {Springer},
  doi       = {10.1134/S1990478920020131}
}

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

@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{Vega26Siriaisa,
  author       = {Vega, Frank},
  title        = {Siriaisa: {A}pproximate {I}ndependent {D}ominating {S}et {S}olver},
  year         = {2026},
  howpublished = {\url{https://pypi.org/project/siriaisa}},
  note         = {Python package version 0.0.8}
}

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

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

@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{tarjan1975efficiency,
  author  = {Tarjan, Robert Endre},
  title   = {Efficiency of a {G}ood {B}ut {N}ot {L}inear {S}et {U}nion {A}lgorithm},
  journal = {Journal of the ACM},
  volume  = {22},
  number  = {2},
  pages   = {215--225},
  year    = {1975},
  doi     = {10.1145/321879.321884}
}

@book{johnson1996cliques,
  editor    = {Johnson, David S. and Trick, Michael A.},
  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   = {Providence, RI, USA},
  year      = {1996},
  doi       = {10.1090/dimacs/026}
}

@misc{npbench,
  author       = {{DynaRoARS}},
  title        = {{NPBench}: {A} collection of benchmarks (in {DIMACS} format) for various {NP}-complete problems},
  howpublished = {GitHub Repository},
  url          = {https://github.com/dynaroars/npbench}
}

@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,
  title     = {SciPy 1.0: fundamental algorithms for scientific computing in Python},
  author    = {Virtanen, Pauli and Gommers, Ralf and Oliphant, Travis E and Haberland, Matt and Reddy, Tyler and Cournapeau, David and Burovski, Evgeni and Peterson, Pearu and Weckesser, Warren and Bright, Jonathan and others},
  journal   = {Nature Methods},
  volume    = {17},
  number    = {3},
  pages     = {261--272},
  year      = {2020},
  publisher = {Nature Publishing Group},
  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}
}

@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{hopcroft1973n52,
  title   = {An $n^{5/2}$ {A}lgorithm for {M}aximum {M}atchings in {B}ipartite {G}raphs},
  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}
}

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

@incollection{alimonti1997improved,
  author    = {Alimonti, Paola and Calamoneri, Tiziana},
  title     = {Improved approximations of independent dominating set in bounded degree graphs},
  booktitle = {Graph-Theoretic Concepts in Computer Science (WG 1996)},
  series    = {Lecture Notes in Computer Science},
  volume    = {1197},
  pages     = {2--16},
  publisher = {Springer},
  address   = {Berlin, Heidelberg},
  year      = {1997},
  doi       = {10.1007/3-540-62559-3_2}
}

@incollection{alimonti1997hardness,
  author    = {Alimonti, Paola and Kann, Viggo},
  title     = {Hardness of approximating problems on cubic graphs},
  booktitle = {Algorithms and Complexity (CIAC 1997)},
  series    = {Lecture Notes in Computer Science},
  volume    = {1203},
  pages     = {288--298},
  publisher = {Springer},
  address   = {Berlin, Heidelberg},
  year      = {1997},
  doi       = {10.1007/3-540-62592-5_80}
}

@article{manlove1999algorithmic,
  author  = {Manlove, David F.},
  title   = {On the algorithmic complexity of twelve covering and independence parameters of graphs},
  journal = {Discrete Applied Mathematics},
  volume  = {91},
  number  = {1--3},
  pages   = {155--175},
  year    = {1999},
  doi     = {10.1016/S0166-218X(98)00147-4}
}

@article{bazgan2020domination,
  author  = {Bazgan, Cristina and Brankovic, Ljiljana and Casel, Katrin and Fernau, Henning},
  title   = {Domination chain: {C}haracterisation, classical complexity, parameterised complexity and approximability},
  journal = {Discrete Applied Mathematics},
  volume  = {280},
  pages   = {23--42},
  year    = {2020},
  doi     = {10.1016/j.dam.2019.10.005}
}

@misc{crescenzi2000compendium,
  author       = {Crescenzi, Pierluigi and Kann, Viggo},
  title        = {A compendium of {NP} optimization problems: {M}inimum {I}ndependent {D}ominating {S}et},
  year         = {2000},
  howpublished = {Online compendium},
  url          = {https://www.csc.kth.se/~viggo/wwwcompendium/node14.html}
}

@incollection{damian1999hardness,
  author    = {Damian-Iordache, Mirela and Pemmaraju, Sriram V.},
  title     = {Hardness of approximating independent domination in circle graphs},
  booktitle = {Algorithms and Computation (ISAAC 1999)},
  series    = {Lecture Notes in Computer Science},
  volume    = {1741},
  pages     = {56--69},
  publisher = {Springer},
  address   = {Berlin, Heidelberg},
  year      = {1999},
  doi       = {10.1007/3-540-46632-0_7}
}

@misc{Vega26Satypy,
  author       = {Vega, Frank},
  title        = {SatyPy: {A} {SAT} {S}olver},
  year         = {2026},
  howpublished = {\url{https://pypi.org/project/satypy}},
  note         = {Python package version 0.0.4}
}