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 2 / Nov 03, 2026 / CC BY 4.0

Abstract

The Minimum Independent Dominating Set problem asks for a smallest maximal independent set of a graph. Unless P=NP\mathrm{P}=\mathrm{NP} it is not approximable within n1−εn^{1-\varepsilon} for any ε>0\varepsilon>0; it is NP-complete on cubic planar bipartite graphs and NP-hard to approximate within δB\delta B on bipartite graphs of maximum degree BB. We present version 0.0.9 of \textsc{Siriaisa}, an ensemble of eighteen strategies that adapts the vertex cover algorithm \textsc{Salvador} and the independent set algorithm \textsc{Esperanza} to independent domination: its exact subproblems are forests, solved by a conditioned tree dynamic program, in place of the bipartite structures of \textsc{Salvador}; one base strategy splits every vertex of degree larger than ⌊n⌋\lfloor\sqrt n\rfloor into unconnected copies; and the improvers include a weighted swap search. We prove that the output is an independent dominating set computed in O(n+m)O(n+m) expected time, with ratio at most Δ\Delta, optimal on forests, and with ratio at most n\sqrt n on three classes of graphs. The degree-splitting strategy computes a dominating set of size at most ⌊n⌋ (i(G)+s(G))\lfloor\sqrt n\rfloor\,(i(G)+s(G)) on every graph, for an explicit splitting excess s(G)s(G), and the output satisfies the same bound when the decoded set is independent. The excess is at most n(n+1)n(\sqrt n+1), largest on complete graphs, zero for n≥D2n\ge D^2 on every family of bounded degree DD, among them the NP-hard and UG-hard bounded-degree families, and O(n)O(\sqrt n) on planar graphs; on complete multipartite, crown, wheel and double-star graphs the output is optimal. We conjecture the ratio O(n)O(\sqrt n) on all graphs; a proof would imply P=NP\mathrm{P}=\mathrm{NP}. In a reduction from satisfiability, every independent dominating set of the graph of a formula with NN variables and tt copies of every clause, tt at least the largest clause width WW, is a satisfying assignment, with NN vertices, or has at least t+Nt+N vertices; with t=Wt=W, every independent dominating set of ratio smaller than 1+W/N1+W/N is a satisfying assignment. This proves the n1−εn^{1-\varepsilon} inapproximability directly from satisfiability, without a gap from the PCP theorem. Through a reduction of Chleb{\'\i}k and Chleb{\'\i}kov{\'a}, with an explicit edge gadget that turns a graph HH into a graph h(H)h(H) with i(h(H))=τ(H)+2∣E(H)∣i(h(H))=\tau(H)+2|E(H)|, where τ(H)\tau(H) is the minimum vertex cover size, every output on h(H)h(H) decodes into a vertex cover of HH; we state the conditional consequences under the Unique Games Conjecture, for which a proof has been reported but not yet peer reviewed, on general graphs and, through the result of Austrin, Khot and Safra, on bounded-degree graphs. In reproducible experiments the output is optimal on 9 9999\,999 of 10 00010\,000 graphs with an exact integer-program optimum, on all 9595 of 112112 bipartite graphs whose optimum was proved, on all 1818 instances of the set cover reduction, and on 22 of the 3030 instances of the vertex cover reduction with a proved optimum; on ten Khot--Regev YES instances the decoded vertex cover has ratio between 1.251.25 and 1.86651.8665. We also report the results on the 6868 complements of the DIMACS clique benchmark.

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 35 referencesShow fewer references
  1. Gaspers, Serge; Liedloff, Mathieu. A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set. Discrete Mathematics and Theoretical Computer Science, vol. 14, no. 1, pp. 29–42. 2012
  2. Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis Th. Fast algorithms for min independent dominating set. Discrete Applied Mathematics, vol. 161, no. 4, pp. 558–572. 2013
  3. Laforest, Christian; Phan, Raphaël. Solving the minimum independent domination set problem in graphs by exact algorithm and greedy heuristic. RAIRO – Operations Research, vol. 47, no. 3, pp. 199–221. 2013
  4. Haraguchi, Kazuya. An Efficient Local Search for the Minimum Independent Dominating Set Problem. 17th International Symposium on Experimental Algorithms (SEA 2018), vol. 103, pp. 13:1–13:13. 2018DOI
  5. Goddard, Wayne; Henning, Michael A. Independent domination in graphs: A survey and recent results. Discrete Mathematics, vol. 313, pp. 839–854. 2013
  6. Lenzen, Christoph; Pignolet, Yvonne-Anne; Wattenhofer, Roger. Distributed minimum dominating set approximations in restricted families of graphs. Distributed Computing, vol. 26, no. 2, pp. 119–137. 2013
  7. 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
  8. 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
  9. 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
  10. Vega, Frank. Siriaisa: Approximate Independent Dominating Set Solver. 2026. Python package version 0.0.9. https://pypi.org/project/siriaisalink
  11. 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
  12. Vega, Frank. Salvador: Approximate Vertex Cover Solver. 2026. Python package version 0.1.4. https://pypi.org/project/salvadorlink
  13. Vega, Frank. Esperanza: Approximate Independent Set Solver. 2026. Python package version 0.1.6. https://pypi.org/project/esperanzalink
  14. 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
  15. 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
  16. Caro, Yair. New results on the independence number. 1979
  17. Wei, Victor K. A lower bound on the stability number of a simple graph. no. Technical Memorandum 81-11217-9. 1981
  18. 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
  19. Cook, Stephen A. The Complexity of Theorem-Proving Procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151–158. 1971DOI
  20. 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
  21. Huangfu, Qi; Hall, J. A. Julian. Parallelizing the dual revised simplex method. Mathematical Programming Computation, vol. 10, no. 1, pp. 119–142. 2018DOI
  22. Nemhauser, George L.; Trotter, Leslie E. Vertex packings: Structural properties and algorithms. Mathematical Programming, vol. 8, no. 1, pp. 232–248. 1975DOI
  23. 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
  24. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. American Mathematical Society, vol. 26. 1996DOI
  25. DynaRoARS. NPBench: A collection of benchmarks (in DIMACS format) for various NP-complete problems. GitHub Repositorylink

Version history

  1. v1 · 34 pagesSubmitted by Frank VegaInitial depositSupersededNov 03, 2026
  2. v2 · 30 pagesSubmitted by Frank VegaSubmitted as a new versionCurrentNov 15, 2026