HEXAGONbeta

The Siriaisa Algorithm for Minimum Independent Dominating Set

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

Contributed by Frank Vega ↗

Version 1 / Nov 03, 2026 / CC BY 4.0

Abstract

The Minimum Independent Dominating Set problem (MIDS) asks for a smallest maximal independent set of an undirected graph; unless P=NP\mathrm{P}=\mathrm{NP}, it cannot be approximated within n1−εn^{1-\varepsilon} for any ε>0\varepsilon>0. We present version 0.0.8 of \textsc{Siriaisa}, an ensemble of eighteen strategies that adapts the vertex cover algorithm \textsc{Salvador} and the independent set algorithm \textsc{Esperanza} to MIDS, with every exact subproblem a forest solved by a conditioned tree dynamic program. We prove that the output is an independent dominating set computed in O((n+m) αA(n))O((n+m)\,\alpha_{\mathrm A}(n)) expected time, that its ratio is at most Δ\Delta, that it is optimal on forests, and that its ratio is at most n\sqrt n on three classes of graphs. A degree-splitting strategy yields a dominating set of size at most ⌊n⌋ (i(G)+s(G))\lfloor\sqrt n\rfloor\,(i(G)+s(G)) for an explicit splitting excess s(G)s(G), which vanishes on bounded-degree families for large nn and is largest on complete graphs, where the output is optimal. More generally, splitting at ⌊n1−ε⌋\lfloor n^{1-\varepsilon}\rfloor gives the bound n1−ε (i(G)+sε(G))n^{1-\varepsilon}\,(i(G)+s_\varepsilon(G)) for every ε∈(0,1]\varepsilon\in(0,1]. We state the ratio n3/4n^{3/4} as a conjecture whose proof would imply P=NP\mathrm{P}=\mathrm{NP}. Through a reduction of Chleb{\'\i}k and Chleb{\'\i}kov{\'a}, every output decodes into a vertex cover, with conditional consequences for the Unique Games Conjecture. In experiments the output is optimal on 9 9999\,999 of 10 00010\,000 graphs with an exact integer-program optimum and on all 9595 bipartite graphs whose optimum was proved. As an application, we analyse the SAT solver \texttt{satypy} 0.0.4: it answers every unsatisfiable formula correctly, every SATISFIABLE answer carries a satisfying assignment, a wrong answer requires a ratio larger than 2p2p for pp variables, and its construction gives a self-contained proof of Halld{\'o}rsson's inapproximability theorem.

Provenance statement

The author designed the strategies of Siriaisa, and used Claude Opus 5.5 to implement them by vibe coding, to write the experiment scripts of the folder car/, and to improve the readability of this manuscript; the author ran all the experiments. 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.

Tools used

Anthropic
Claude OpusVersion 5.5

References

  1. Irving, Robert W. On approximating the minimum independent dominating set. Information Processing Letters, vol. 37, no. 4, pp. 197–200. 1991DOI
  2. Halldórsson, Magnús M. Approximating the minimum maximal independence number. Information Processing Letters, vol. 46, no. 4, pp. 169–172. 1993DOI
  3. Damian-Iordache, Mirela; Pemmaraju, Sriram V. Hardness of approximating independent domination in circle graphs. Algorithms and Computation (ISAAC 1999), vol. 1741, pp. 56–69. 1999DOI
  4. Loverov, Ya. A.; Orlovich, Yu. L. NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs. Journal of Applied and Industrial Mathematics, vol. 14, no. 2, pp. 352–366. 2020DOI
  5. Manlove, David F. On the algorithmic complexity of twelve covering and independence parameters of graphs. Discrete Applied Mathematics, vol. 91, no. 1–3, pp. 155–175. 1999DOI
  6. Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning. Domination chain: Characterisation, classical complexity, parameterised complexity and approximability. Discrete Applied Mathematics, vol. 280, pp. 23–42. 2020DOI
  7. Crescenzi, Pierluigi; Kann, Viggo. A compendium of NP optimization problems: Minimum Independent Dominating Set. 2000. Online compendiumlink
  8. Alimonti, Paola; Calamoneri, Tiziana. Improved approximations of independent dominating set in bounded degree graphs. Graph-Theoretic Concepts in Computer Science (WG 1996), vol. 1197, pp. 2–16. 1997DOI
  9. Alimonti, Paola; Kann, Viggo. Hardness of approximating problems on cubic graphs. Algorithms and Complexity (CIAC 1997), vol. 1203, pp. 288–298. 1997DOI
  10. Chlebík, Miroslav; Chlebíková, Janka. Approximation hardness of dominating set problems in bounded degree graphs. Information and Computation, vol. 206, no. 11, pp. 1264–1275. 2008DOI
Show all 29 referencesShow fewer references
  1. 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
  2. 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
  3. 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
  4. Vega, Frank. Siriaisa: Approximate Independent Dominating Set Solver. 2026. Python package version 0.0.8. https://pypi.org/project/siriaisalink
  5. Vega, Frank. An Approximate Solution to the Minimum Vertex Cover Problem: The Salvador Algorithm. 2026. Manuscript; preprint at https://www.preprints.org/manuscript/202605.2000link
  6. Vega, Frank. Salvador: Approximate Vertex Cover Solver. 2026. Python package version 0.1.4. https://pypi.org/project/salvadorlink
  7. Vega, Frank. Esperanza: Approximate Independent Set Solver. 2026. Python package version 0.1.6. https://pypi.org/project/esperanzalink
  8. 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
  9. Hagberg, Aric A.; Schult, Daniel A.; Swart, Pieter J. Exploring network structure, dynamics, and function using NetworkX. Proceedings of the 7th Python in Science Conference (SciPy 2008), pp. 11–15. 2008
  10. Caro, Yair. New results on the independence number. 1979
  11. Wei, Victor K. A lower bound on the stability number of a simple graph. no. Technical Memorandum 81-11217-9. 1981
  12. 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
  13. Vega, Frank. SatyPy: A SAT Solver. 2026. Python package version 0.0.4. https://pypi.org/project/satypylink
  14. Virtanen, Pauli; Gommers, Ralf; Oliphant, Travis E; Haberland, Matt; Reddy, Tyler; Cournapeau, David; Burovski, Evgeni; Peterson, Pearu; Weckesser, Warren; Bright, Jonathan; others. SciPy 1.0: fundamental algorithms for scientific computing in Python. Nature Methods, vol. 17, no. 3, pp. 261–272. 2020DOI
  15. Huangfu, Qi; Hall, J. A. Julian. Parallelizing the dual revised simplex method. Mathematical Programming Computation, vol. 10, no. 1, pp. 119–142. 2018DOI
  16. Nemhauser, George L.; Trotter, Leslie E. Vertex packings: Structural properties and algorithms. Mathematical Programming, vol. 8, no. 1, pp. 232–248. 1975DOI
  17. 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
  18. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. American Mathematical Society, vol. 26. 1996DOI
  19. DynaRoARS. NPBench: A collection of benchmarks (in DIMACS format) for various NP-complete problems. GitHub Repositorylink

Version history

  1. v1Submitted by Frank VegaInitial depositCurrentNov 03, 2026