The Siriaisa Algorithm for Minimum Independent Dominating Set

The Minimum Independent Dominating Set problem (MIDS) asks for a smallest maximal independent set of an undirected graph; unless $\mathrm{P}=\mathrm{NP}$, it cannot be approximated within $n^{1-\varepsilon}$ for any $\varepsilon>0$. We present version 0.0.8 of Siriaisa, an ensemble of eighteen strategies that adapts the vertex cover algorithm Salvador and the independent set algorithm 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)\,\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 $\sqrt n$ on three classes of graphs. A degree-splitting strategy yields a dominating set of size at most $\lfloor\sqrt n\rfloor\,(i(G)+s(G))$ for an explicit splitting excess $s(G)$, which vanishes on bounded-degree families for large $n$ and is largest on complete graphs, where the output is optimal. More generally, splitting at $\lfloor n^{1-\varepsilon}\rfloor$ gives the bound $n^{1-\varepsilon}\,(i(G)+s_\varepsilon(G))$ for every $\varepsilon\in(0,1]$. We state the ratio $n^{3/4}$ as a conjecture whose proof would imply $\mathrm{P}=\mathrm{NP}$. Through a reduction of Chlebík and Chlebíková, every output decodes into a vertex cover, with conditional consequences for the Unique Games Conjecture. In experiments the output is optimal on $9\,999$ of $10\,000$ graphs with an exact integer-program optimum and on all $95$ bipartite graphs whose optimum was proved. As an application, we analyse the SAT solver 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 $2p$ for $p$ variables, and its construction gives a self-contained proof of Halldórsson's inapproximability theorem.