The Siriaisa Algorithm for Minimum Independent Dominating Set
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 it is not approximable within for any ; it is NP-complete on cubic planar bipartite graphs and NP-hard to approximate within on bipartite graphs of maximum degree . 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 into unconnected copies; and the improvers include a weighted swap search. We prove that the output is an independent dominating set computed in expected time, with ratio at most , optimal on forests, and with ratio at most on three classes of graphs. The degree-splitting strategy computes a dominating set of size at most on every graph, for an explicit splitting excess , and the output satisfies the same bound when the decoded set is independent. The excess is at most , largest on complete graphs, zero for on every family of bounded degree , among them the NP-hard and UG-hard bounded-degree families, and on planar graphs; on complete multipartite, crown, wheel and double-star graphs the output is optimal. We conjecture the ratio on all graphs; a proof would imply . In a reduction from satisfiability, every independent dominating set of the graph of a formula with variables and copies of every clause, at least the largest clause width , is a satisfying assignment, with vertices, or has at least vertices; with , every independent dominating set of ratio smaller than is a satisfying assignment. This proves the 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 into a graph with , where is the minimum vertex cover size, every output on decodes into a vertex cover of ; 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 of graphs with an exact integer-program optimum, on all of bipartite graphs whose optimum was proved, on all instances of the set cover reduction, and on of the instances of the vertex cover reduction with a proved optimum; on ten Khot--Regev YES instances the decoded vertex cover has ratio between and . We also report the results on the complements of the DIMACS clique benchmark.
Provenance statement
Tools used
- Anthropic
- Claude OpusVersion 5.5
References
- Irving, Robert W. On approximating the minimum independent dominating set. Information Processing Letters, vol. 37, no. 4, pp. 197–200. 1991DOI
- Halldórsson, Magnús M. Approximating the minimum maximal independence number. Information Processing Letters, vol. 46, no. 4, pp. 169–172. 1993DOI
- 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
- 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
- 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
- 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
- Crescenzi, Pierluigi; Kann, Viggo. A compendium of NP optimization problems: Minimum Independent Dominating Set. 2000. Online compendiumlink
- 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
- Alimonti, Paola; Kann, Viggo. Hardness of approximating problems on cubic graphs. Algorithms and Complexity (CIAC 1997), vol. 1203, pp. 288–298. 1997DOI
- 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
- 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
- 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
- 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
- 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
- Goddard, Wayne; Henning, Michael A. Independent domination in graphs: A survey and recent results. Discrete Mathematics, vol. 313, pp. 839–854. 2013
- 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
- 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
- Khot, Subhash; Regev, Oded. Vertex Cover Might Be Hard to Approximate to Within . Journal of Computer and System Sciences, vol. 74, no. 3, pp. 335–349. 2008DOI
- 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
- Vega, Frank. Siriaisa: Approximate Independent Dominating Set Solver. 2026. Python package version 0.0.9. https://pypi.org/project/siriaisalink
- 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
- Vega, Frank. Salvador: Approximate Vertex Cover Solver. 2026. Python package version 0.1.4. https://pypi.org/project/salvadorlink
- Vega, Frank. Esperanza: Approximate Independent Set Solver. 2026. Python package version 0.1.6. https://pypi.org/project/esperanzalink
- 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
- 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
- Caro, Yair. New results on the independence number. 1979
- Wei, Victor K. A lower bound on the stability number of a simple graph. no. Technical Memorandum 81-11217-9. 1981
- 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
- Cook, Stephen A. The Complexity of Theorem-Proving Procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151–158. 1971DOI
- 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
- Huangfu, Qi; Hall, J. A. Julian. Parallelizing the dual revised simplex method. Mathematical Programming Computation, vol. 10, no. 1, pp. 119–142. 2018DOI
- Nemhauser, George L.; Trotter, Leslie E. Vertex packings: Structural properties and algorithms. Mathematical Programming, vol. 8, no. 1, pp. 232–248. 1975DOI
- Hopcroft, John E.; Karp, Richard M. An Algorithm for Maximum Matchings in Bipartite Graphs. SIAM Journal on Computing, vol. 2, no. 4, pp. 225–231. 1973DOI
- Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. American Mathematical Society, vol. 26. 1996DOI
- DynaRoARS. NPBench: A collection of benchmarks (in DIMACS format) for various NP-complete problems. GitHub Repositorylink
Version history
- v1 · 34 pagesSubmitted by Frank VegaInitial depositSupersededNov 03, 2026
- v2 · 30 pagesSubmitted by Frank VegaSubmitted as a new versionCurrentNov 15, 2026