%% \documentclass[preprint,review,12pt]{elsarticle}
%% Use the options 1p,twocolumn; 3p; 3p,twocolumn; 5p; or 5p,twocolumn
%% for a journal layout.
\documentclass[final,3p,times]{elsarticle}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{url}
\usepackage{hyperref}
\hypersetup{colorlinks=true,allcolors=blue}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{caption}
\usepackage{microtype}
\usepackage{enumitem}
\usepackage{xcolor}
\usepackage{tabularx}
\usepackage{booktabs}
\usepackage{siunitx}
\usepackage{array}
\usepackage{float}
\usepackage{longtable}
\usepackage{graphicx}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning,calc}
\makeatletter
\providecommand{\theHALG@line}{}
\renewcommand{\theHALG@line}{\thealgorithm.\arabic{ALG@line}}
\makeatother
\theoremstyle{plain}
\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Corollary}[Theorem]{Corollary}
\newtheorem{Conjecture}[Theorem]{Conjecture}
\theoremstyle{definition}
\newtheorem{Definition}[Theorem]{Definition}
\newtheorem{Example}[Theorem]{Example}
\newtheorem{Remark}[Theorem]{Remark}
\journal{Hexagon}
\begin{document}
\begin{frontmatter}
\title{The Siriaisa Algorithm for Minimum Independent Dominating Set}
\author{Frank Vega}
\address{Information Physics Institute, 840 W 67th St, Hialeah, FL 33012, USA}
\ead{vega.frank@gmail.com}
\begin{abstract}
The Minimum Independent Dominating Set problem asks for a smallest maximal independent set of a graph. Unless $\mathrm{P}=\mathrm{NP}$ it is not approximable within $n^{1-\varepsilon}$ for any $\varepsilon>0$; it is NP-complete on cubic planar bipartite graphs and NP-hard to approximate within $\delta B$ on bipartite graphs of maximum degree $B$. 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 $\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)$ expected time, with ratio at most $\Delta$, optimal on forests, and with ratio at most $\sqrt n$ on three classes of graphs. The degree-splitting strategy computes a dominating set of size at most $\lfloor\sqrt n\rfloor\,(i(G)+s(G))$ on every graph, for an explicit splitting excess $s(G)$, and the output satisfies the same bound when the decoded set is independent. The excess is at most $n(\sqrt n+1)$, largest on complete graphs, zero for $n\ge D^2$ on every family of bounded degree $D$, among them the NP-hard and UG-hard bounded-degree families, and $O(\sqrt n)$ on planar graphs; on complete multipartite, crown, wheel and double-star graphs the output is optimal. We conjecture the ratio $O(\sqrt n)$ on all graphs; a proof would imply $\mathrm{P}=\mathrm{NP}$. In a reduction from satisfiability, every independent dominating set of the graph of a formula with $N$ variables and $t$ copies of every clause, $t$ at least the largest clause width $W$, is a satisfying assignment, with $N$ vertices, or has at least $t+N$ vertices; with $t=W$, every independent dominating set of ratio smaller than $1+W/N$ is a satisfying assignment. This proves the $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 $H$ into a graph $h(H)$ with $i(h(H))=\tau(H)+2|E(H)|$, where $\tau(H)$ is the minimum vertex cover size, every output on $h(H)$ decodes into a vertex cover of $H$; 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\,999$ of $10\,000$ graphs with an exact integer-program optimum, on all $95$ of $112$ bipartite graphs whose optimum was proved, on all $18$ instances of the set cover reduction, and on $2$ of the $30$ instances of the vertex cover reduction with a proved optimum; on ten Khot--Regev YES instances the decoded vertex cover has ratio between $1.25$ and $1.8665$. We also report the results on the $68$ complements of the DIMACS clique benchmark.
\end{abstract}
\begin{keyword}
Minimum Independent Dominating Set \sep Minimum Maximal Independent Set \sep Approximation Algorithm \sep Forest Dynamic Programming \sep Local Search \sep Bipartite Graphs \sep Unique Games Conjecture \sep P versus NP
\MSC[2020] 05C69 \sep 68Q25 \sep 68W25 \sep 90C27
\end{keyword}
\end{frontmatter}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{sec:intro}
An \emph{independent dominating set} of an undirected graph $G=(V,E)$ is a set $D\subseteq V$ in which no two vertices are adjacent and every vertex of $V\setminus D$ has a neighbour in $D$; equivalently, $D$ is a maximal independent set. The Minimum Independent Dominating Set problem (MIDS) asks for such a set of minimum size, denoted $i(G)$. We write $n=|V|$, $m=|E|$, $N(v)$ and $N[v]=N(v)\cup\{v\}$ for the open and closed neighbourhoods, $\deg(v)=|N(v)|$, $\Delta$ for the maximum degree, $\tau(G)$ for the minimum vertex cover size and $\alpha(G)$ for the independence number. The ratio of a returned independent dominating set $S$ is $\rho=|S|/i(G)$.
MIDS is among the hardest graph problems to approximate. Irving proved that, unless $\mathrm{P}=\mathrm{NP}$, no polynomial-time algorithm approximates it within any constant factor~\cite{irving1991approximating}, and Halld{\'o}rsson proved that it cannot be approximated within $n^{1-\varepsilon}$ for any $\varepsilon>0$ unless $\mathrm{P}=\mathrm{NP}$~\cite{halldorsson1993approximating}; Damian-Iordache and Pemmaraju proved that it is NP-complete on circle graphs and, unless $\mathrm{P}=\mathrm{NP}$, not approximable within $n^{\varepsilon}$ for any $\varepsilon<1$ on circle graphs with $n$ vertices~\cite{damian1999hardness}. The problem remains NP-hard on bipartite graphs: Loverov and Orlovich proved that it is NP-complete already on cubic planar bipartite graphs~\cite{loverov2020np}; Manlove proved it NP-hard on cubic planar graphs~\cite{manlove1999algorithmic}, and Bazgan, Brankovic, Casel and Fernau derived from Manlove's reduction that it is APX-hard on cubic graphs~\cite{bazgan2020domination}. On graphs of maximum degree at most a constant $B$, every maximal independent set approximates MIDS within $B$, and the problem is APX-complete~\cite{crescenzi2000compendium}; on cubic graphs, Alimonti and Calamoneri gave a polynomial-time algorithm with ratio $1.923$, and the ratio $2$ on graphs of maximum degree at most $3$~\cite{alimonti1997improved}, while Alimonti and Kann proved APX-completeness on cubic graphs of vertex cover, independent set and dominating set~\cite{alimonti1997hardness}. It is also hard to approximate on graphs of bounded degree, including bipartite ones: Chleb{\'\i}k and Chleb{\'\i}kov{\'a} proved that there are absolute constants $\delta>0$ and $B_0$ such that for every $B\ge B_0$ MIDS is NP-hard to approximate within $\delta B$ on graphs of maximum degree at most $B$, and that the same holds on bipartite graphs; for small degrees they obtained the NP-hard factors $1+\frac1{680}$ for $\Delta\le3$, and $1+\frac1{293}$ and $1+\frac1{151}$ for bipartite graphs with $\Delta\le4$ and $\Delta\le5$~\cite{chlebik2008approximation}. These results hold without any conjecture.
\paragraph{Exact algorithms and heuristics} A minimum independent dominating set can be computed in $O(1.4423^n)$ time by enumerating the maximal independent sets; Gaspers and Liedloff gave a branch-and-reduce algorithm that runs in $O(1.3569^n)$ time, with a lower bound $\Omega(1.3247^n)$ on its worst-case running time~\cite{gaspers2012branch}, and Bourgeois, Della Croce, Escoffier and Paschos gave further exact algorithms~\cite{bourgeois2013fast}. Laforest and Phan proposed an exact algorithm and a greedy heuristic~\cite{laforest2013solving}. Haraguchi proposed a local search whose move, the $k$-swap, drops $k$ vertices of a maximal independent set and adds any number of vertices: an improved solution in the neighbourhood is found, or shown not to exist, in $O(n\Delta)$ time for $k=2$, and in $O(n\Delta^3)$ time for $k=3$ when the solution is minimal with respect to the $2$-swap; a metaheuristic that iterates this search was evaluated on DIMACS graphs~\cite{haraguchi2018efficient}. Goddard and Henning survey independent domination in graphs~\cite{goddard2013independent}. For the Minimum Dominating Set problem, in which the set need not be independent, Lenzen, Pignolet and Wattenhofer gave a distributed algorithm that computes a constant-factor approximation on planar graphs in a constant number of rounds~\cite{lenzen2013distributed}.
Under the Unique Games Conjecture (UGC)~\cite{khot2002unique}, Khot and Regev proved that Minimum Vertex Cover is hard to approximate within $2-\varepsilon$ for every $\varepsilon>0$~\cite{khot2008vertex}. In October 2026 the OpenAI Math Team released a manuscript with Lean artifacts reporting a proof of UGC in the NP-hardness form that the theorem of Khot and Regev requires~\cite{openai2026ugc}; at the time of writing it has not been peer reviewed. If it holds, the hardness result of Khot and Regev holds unless $\mathrm{P}=\mathrm{NP}$. Through a reduction of Chleb{\'\i}k and Chleb{\'\i}kov{\'a} (Section~\ref{sec:hardness}), every vertex cover instance $H$ becomes an MIDS instance $h(H)$ whose optimum is $\tau(H)$ plus a known constant, so the instances of Khot and Regev give MIDS instances on which Siriaisa can be tested as a vertex cover algorithm.
This paper describes version 0.0.9 of \textsc{Siriaisa}~\cite{Vega26Siriaisa}, a Python implementation of an ensemble of eighteen strategies. The ensemble adapts the seventeen strategies of the vertex cover algorithm \textsc{Salvador}~\cite{Vega26SalvadorPaper,Vega26Salvador} and the phases of the independent set algorithm \textsc{Esperanza}~\cite{Vega26} to independent domination. Where \textsc{Salvador} builds a bipartite structure and solves vertex cover on it exactly by K\H{o}nig's theorem, \textsc{Siriaisa} builds a \emph{forest} and solves MIDS on it exactly by a linear-time tree dynamic program; MIDS is NP-hard on bipartite graphs~\cite{loverov2020np}, so the bipartite structures of \textsc{Salvador} carry no exact solver for MIDS. One base strategy splits every vertex of degree larger than $\lfloor\sqrt n\rfloor$ into copies, so that the auxiliary graph has maximum degree at most $\lfloor\sqrt n\rfloor$.
\paragraph{Contributions} The contributions of this paper are:
\begin{itemize}
\item The algorithm (Section~\ref{sec:algorithm}): twelve base strategies, five improvers and a final refinement, an exact conditioned forest solver, induced-forest layers, a degree-splitting strategy at $\lfloor\sqrt n\rfloor$, and a weighted swap search, together with the proof that the output is an independent dominating set (Theorem~\ref{thm:correctness}).
\item The running time $O(n+m)$, in expectation, for the default parameters (Theorem~\ref{thm:runtime}).
\item Proved bounds (Section~\ref{sec:ratio}): the ratio is at most $\Delta$ on every graph (Corollary~\ref{cor:delta}); the output is optimal on every forest (Theorem~\ref{thm:forest}); the ratio is at most $\sqrt n$ on three classes (Theorem~\ref{thm:sqrt}); and the degree-splitting strategy yields a dominating set of size at most $\lfloor\sqrt n\rfloor\,(i(G)+s(G))$ on every graph, for an explicit splitting excess $s(G)$, with the same bound for the output when the decoded set is independent (Theorem~\ref{thm:split}); the excess is largest on complete graphs, of order $n^{3/2}$, it vanishes for $n\ge D^2$ on every family of bounded degree $D$, among them the NP-hard and UG-hard bounded-degree families, it is $O(\sqrt n)$ on planar graphs, and on complete multipartite, crown, wheel and double-star graphs the output is optimal (Propositions~\ref{prop:sworst}, \ref{prop:complete} and~\ref{prop:families}, Table~\ref{tab:sfamilies}).
\item The conjecture that the ratio is $O(\sqrt n)$ on every graph, with the theorem that a proof would imply $\mathrm{P}=\mathrm{NP}$ (Conjecture~\ref{conj:sqrt}, Theorem~\ref{thm:sqrtpnp}), and the graphs on which its bound is proved (Proposition~\ref{prop:conjfamilies}).
\item A reduction from satisfiability (Section~\ref{sec:sat}): the graph of a formula with $t$ copies of every clause, $t$ at least the largest clause width, whose independent dominating sets are the satisfying assignments, with one vertex per variable, or have at least $t$ more vertices (Theorem~\ref{thm:satgraph}, Corollary~\ref{cor:satratio}); it proves that MIDS is not approximable within $n^{1-\varepsilon}$ for any $\varepsilon>0$ unless $\mathrm{P}=\mathrm{NP}$, directly from satisfiability and without a gap from the PCP theorem (Theorem~\ref{thm:satinapprox}).
\item The vertex cover reduction of Chleb{\'\i}k and Chleb{\'\i}kov{\'a} with an explicit gadget and the identity $i(h(H))=\tau(H)+2|E(H)|$ (Proposition~\ref{prop:vcids}), the decoding of every independent dominating set into a vertex cover (Lemma~\ref{lem:decode}), and the conditional consequences for vertex cover approximation, on general graphs under the hardness of Khot and Regev and on bounded-degree graphs under that of Austrin, Khot and Safra (Theorem~\ref{thm:ugc}, Corollary~\ref{cor:aks}).
\item Reproducible experiments (Section~\ref{sec:experiments}): $10\,000$ structured and random graphs with an exact integer-program optimum, with four baseline heuristics on the same graphs (Section~\ref{sec:baselines}); $112$ bipartite graphs; $55$ instances of the two reductions of Chleb{\'\i}k and Chleb{\'\i}kov{\'a}, ten of them built from Khot--Regev YES instances; and the $68$ complements of the DIMACS clique benchmark graphs.
\end{itemize}
Section~\ref{sec:data} records the code metadata, Section~\ref{sec:algorithm} describes the algorithm, Section~\ref{sec:correctness} proves correctness, Section~\ref{sec:runtime} the running time and Section~\ref{sec:ratio} the bounds. Section~\ref{sec:hardness} treats the reductions and the conditional consequences, Section~\ref{sec:sat} the reduction from satisfiability, Section~\ref{sec:experiments} reports the experiments and Section~\ref{sec:conclusion} concludes. Table~\ref{tab:notation} lists the notation.
\begin{table}[H]
\centering
\small
\caption{Notation.}
\label{tab:notation}
\begin{tabular}{p{0.36\textwidth}p{0.56\textwidth}}
\toprule
Symbol & Meaning \\
\midrule
$G=(V,E)$, $n$, $m$ & the input graph, its number of vertices and of edges \\
$N(v)$, $N[v]$, $\deg(v)$ & open and closed neighbourhood and degree of $v$ \\
$\Delta$, $\delta(G)$ & maximum and minimum degree \\
$i(G)$ & minimum size of an independent dominating set \\
$\alpha(G)$, $\tau(G)$ & independence number, minimum vertex cover size \\
$S$, $\rho=|S|/i(G)$ & the output of Algorithm~\ref{alg:main} and its ratio \\
$c_1,\dots,c_{18}$ & the candidates of the strategies (Table~\ref{tab:strategies}) \\
$\mathrm{in}$, $\mathrm{pre}$, $\mathrm{force}$, $P$ & flags and penalty of the forest solver (Section~\ref{sec:forestdp}) \\
IN, DOM, FREE & states of a vertex in the forest solver (Section~\ref{sec:forestdp}) \\
$u(c)$, $a(c)$, $\delta(v)$ & terms of the recurrences of the forest solver (Section~\ref{sec:forestdp}) \\
$k=\max(1,\lfloor\sqrt n\rfloor)$ & degree threshold of the splitting strategy $c_{13}$ \\
$B=\{v:\deg(v)>k\}$ & the split vertices (Section~\ref{sec:ratio}) \\
$s(G)$ & splitting excess, $\sum_{v\in B}(\lceil\deg(v)/k\rceil-1)$ \\
$H$ (Section~\ref{sec:ratio}), $S_0$ & copy graph of Algorithm~\ref{alg:split} and decoded set \\
$H$, $m_H$, $h(H)$ (Section~\ref{sec:hardness}) & a vertex cover instance, its number of edges, its VC-IDS graph \\
$\varphi$, $N$, $q$, $W$, $\Lambda$ & a formula, its numbers of variables and clauses, its largest clause width, its number of literal occurrences \\
$G_{\varphi,t}$ & graph of $\varphi$ with $t$ copies of every clause (Definition~\ref{def:satgraph}) \\
\bottomrule
\end{tabular}
\end{table}
\section{Research Data}
\label{sec:data}
The algorithm is implemented in the Python package \texttt{siriaisa}~\cite{Vega26Siriaisa}. The version described in this paper is v0.0.9. Table~\ref{codeMetadata} lists the code metadata.
\begin{table}[H]
\centering
\small
\begin{tabular}{|l|l|l|}
\hline
\textbf{Nr.} & \textbf{Code metadata description} & \textbf{Metadata} \\
\hline
C1 & Current code version & v0.0.9 \\
\hline
C2 & Permanent link to code repository & \url{https://github.com/frankvegadelgado/mids} \\
\hline
C3 & Package name & \texttt{siriaisa} \\
\hline
C4 & Legal Code License & MIT License \\
\hline
C5 & Code versioning system used & git \\
\hline
C6 & Languages, tools, and services used & Python $\geq$ 3.12, NetworkX, NumPy, SciPy \\
\hline
C7 & Main entry points & \texttt{iris}, \texttt{batch\_iris}, \texttt{test\_iris} \\
\hline
\end{tabular}
\caption{Code metadata of the \texttt{siriaisa} package. SciPy is used only by the experiment scripts, for the exact integer programs.}
\label{codeMetadata}
\end{table}
\section{The Siriaisa Algorithm}
\label{sec:algorithm}
The input graph is converted once into an index graph $\mathrm{adj}$ on the vertices $0,\dots,n-1$, and self-loops are removed. Every strategy returns a set that is turned into an independent dominating set by the repair-and-complete routine of Section~\ref{sec:complete}; the strategies are computed in their numbering order, the base strategies $c_1$--$c_{13}$ first and the improvers $c_{14}$--$c_{18}$ last, and the output is $c_{18}$. Table~\ref{tab:strategies} lists them, and Algorithm~\ref{alg:main} gives the main loop.
\begin{table}[H]
\centering
\small
\caption{The eighteen strategies of \textsc{Siriaisa} 0.0.9. ``Source'' names the strategy of \textsc{Salvador}~\cite{Vega26SalvadorPaper} or the phase of \textsc{Esperanza}~\cite{Vega26} that it adapts.}
\label{tab:strategies}
\resizebox{\textwidth}{!}{%
\begin{tabular}{lll}
\toprule
Name & Strategy & Source \\
\midrule
$c_1$ & spanning-tree peeling: maximum spanning forest, tree DP, peel, repeat & --- \\
$c_2$ & endpoints of the NetworkX minimum maximal matching & \textsc{Salvador} $c_2$ \\
$c_3$ & greedy: the undominated vertex that dominates most undominated vertices & \textsc{Salvador} $c_3$ \\
$c_4$ & star-forest reduction solved by the tree DP & \textsc{Salvador} $c_4$ \\
$c_5$ & Min-to-Min & \textsc{Salvador} $c_5$ \\
$c_6$ & primal--dual on the domination linear program & \textsc{Salvador} $c_6$ \\
$c_7$ & BFS spanning forest solved by the tree DP & \textsc{Salvador} $c_7$ \\
$c_8$ & DFS spanning forest solved by the tree DP & \textsc{Salvador} $c_8$ \\
$c_9$ & induced-forest layers, each solved by the tree DP, in several orders & \textsc{Salvador} $c_9$ \\
$c_{10}$ & first forest layer re-solved exactly, the rest fixed from the best of $c_1$--$c_9$ & \textsc{Salvador} $c_{10}$, $c_{12}$ \\
$c_{11}$ & feedback-core peeling and the conditioned forest DP & \textsc{Salvador} $c_{11}$ \\
$c_{12}$ & dynamic minimum-degree (Caro--Wei) greedy & \textsc{Esperanza} baseline \\
$c_{13}$ & degree splitting at $\lfloor\sqrt n\rfloor$, decoding, repair & --- \\
$c_{14}$ & union of $c_2$--$c_8$, repaired by votes & \textsc{Salvador} $c_{13}$ \\
$c_{15}$ & descent and weighted swap search from the best of $c_1$--$c_{14}$ & \textsc{Salvador} $c_{14}$, \textsc{Esperanza} \\
$c_{16}$ & reduce-and-search: swap search and forest large-neighbourhood search & \textsc{Salvador} $c_{15}$ \\
$c_{17}$ & consensus forcing over $c_1$--$c_{16}$ & \textsc{Salvador} $c_{16}$ \\
$c_{18}$ & refinement of every candidate, a longer search on the best & \textsc{Salvador} $c_{17}$, \textsc{Esperanza} \\
\bottomrule
\end{tabular}%
}
\end{table}
\begin{algorithm}[H]
\caption{\textsc{FindIndependentDominatingSet}$(G)$}
\label{alg:main}
\begin{algorithmic}[1]
\Require Undirected graph $G=(V,E)$
\Ensure An independent dominating set of $G$
\State remove self-loops; build the index graph $\mathrm{adj}$; $n\gets|V|$, $m\gets|E|$
\State $c_1\gets\textsc{Complete}(\textsc{SpanningTreePeeling}(\mathrm{adj}))$; $c_2\gets\textsc{Complete}(\text{endpoints of }\texttt{min\_maximal\_matching})$; $c_3\gets\textsc{Complete}(\emptyset)$
\State $c_4,c_7,c_8\gets$ the star, BFS and DFS spanning forests solved by Algorithm~\ref{alg:forestdp} and completed
\State $c_5\gets\textsc{MinToMin}$; $c_6\gets\textsc{PrimalDual}$
\State $(c_9,\mathcal L)\gets\textsc{ForestLayers}(\mathrm{adj})$ \Comment{Algorithm~\ref{alg:layers}; $\mathcal L$ the layers}
\State $c_{10}\gets\textsc{ResolveLayer}(\text{best of }c_1..c_9,L_0)$ if not larger
\State $c_{11}\gets\textsc{FeedbackForest}(\mathrm{adj},\text{best of }c_1..c_{10})$; $c_{12}\gets\textsc{CaroWei}$; $c_{13}\gets\textsc{DegreeSplit}(\mathrm{adj})$ \Comment{Algorithm~\ref{alg:split}}
\State $LB\gets\sum_{\text{components }C}\lceil n_C/(\Delta_C+1)\rceil$ \Comment{Lemma~\ref{lem:lb}}
\State $c_{14}\gets\textsc{Complete}(c_2\cup\dots\cup c_8,\text{priority}=\text{votes})$
\State $c_{15}\gets\textsc{ImproveIDS}(\text{best of }c_1..c_{14})$ \Comment{Algorithm~\ref{alg:improve}}
\State $c_{16}\gets$ three rounds of \textsc{ImproveIDS} followed by \textsc{ForestLNS}$(\mathcal L)$, from the best of $c_1..c_{15}$, each kept if not larger
\State $c_{17}\gets\textsc{ConsensusForce}(c_1,\dots,c_{16})$
\State $R_j\gets\textsc{ImproveIDS}(\textsc{ForestLNS}(c_j,\mathcal L))$ for every distinct $c_j$, $j\le17$
\State $c_{18}\gets\textsc{Complete}(\textsc{ForestLNS}(\textsc{ImproveIDS}(\min_j R_j),\mathcal L))$
\State verify every $c_j$; \Return $c_{18}$
\end{algorithmic}
\end{algorithm}
Every search of lines 10, 11, 13 and 14 stops as soon as its best set has at most $LB$ vertices.
\subsection{Repair and completion}
\label{sec:complete}
Algorithm~\ref{alg:complete} turns any seed into an independent dominating set; it is the counterpart of the pruning of \textsc{Salvador} and of the routine MaximizeSolution of \textsc{Salvador} and \textsc{Esperanza}. All sorts are stable counting sorts on integer keys.
\begin{algorithm}[H]
\caption{\textsc{Complete}$(\mathrm{adj},P,\pi)$}
\label{alg:complete}
\begin{algorithmic}[1]
\Require Index graph, seed $P\subseteq V$, optional integer priority $\pi$
\Ensure An independent dominating set $S$
\State $S\gets P$; $\mathrm{conf}(v)\gets|N(v)\cap S|$ for $v\in S$
\For{$v\in S$ with $\mathrm{conf}(v)>0$, by decreasing $\mathrm{conf}$, then increasing $\pi$, then increasing degree}
\If{$v\in S$ and $\mathrm{conf}(v)>0$} remove $v$ from $S$ and decrement $\mathrm{conf}$ of its neighbours in $S$ \EndIf
\EndFor
\State $U\gets$ the vertices with no vertex of $S$ in their closed neighbourhood; $g(v)\gets|N[v]\cap U|$ for $v\in U$
\While{$U\neq\emptyset$} \Comment{bucket queue on $g$}
\State take $v\in U$ of largest $g(v)$; $S\gets S\cup\{v\}$; remove $N[v]\cap U$ from $U$ and update $g$ on their neighbours
\EndWhile
\State \Return $S$
\end{algorithmic}
\end{algorithm}
\subsection{The conditioned forest solver}
\label{sec:forestdp}
Let $F$ be an induced forest of $G$ and let the rest of $G$ be fixed. Every vertex $v$ of $F$ carries three flags: $\mathrm{in}(v)$ ($v$ may be selected; false when $v$ has a selected neighbour outside $F$), $\mathrm{pre}(v)$ ($v$ is already dominated from outside $F$) and $\mathrm{force}(v)$ ($v$ is the only possible dominator of some vertex outside $F$). With a penalty $P>|F|$, Algorithm~\ref{alg:forestdp} minimises
\[
\Phi(X)=|X|+P\cdot\bigl|\{v\in V(F):v\notin X\cup N(X),\ \neg\mathrm{pre}(v)\}\bigr|+P\cdot\bigl|\{v:\mathrm{force}(v),\ v\notin X\}\bigr|
\]
over the sets $X\subseteq V(F)$ that are independent and contain only vertices with $\mathrm{in}(v)$. Rooting every tree, the states of a vertex $v$ are IN ($v\in X$), DOM ($v\notin X$, dominated by a child or from outside) and FREE ($v\notin X$, not dominated by its children). With $u(c)=0$ if $\mathrm{pre}(c)$ and $u(c)=P$ otherwise, and $a(c)=\min(\mathrm{DOM}(c),\mathrm{FREE}(c)+u(c))$, the recurrences over the children $c$ of $v$ are
\begin{align*}
\mathrm{IN}(v)&=\begin{cases}1+\sum_c\min(\mathrm{DOM}(c),\mathrm{FREE}(c)) & \text{if }\mathrm{in}(v),\\ \infty & \text{otherwise,}\end{cases}\\
\mathrm{FREE}(v)&=\textstyle\sum_c a(c)+P\cdot[\mathrm{force}(v)],\\
\mathrm{DOM}(v)&=\textstyle\sum_c\min(\mathrm{IN}(c),a(c))+\delta(v)+P\cdot[\mathrm{force}(v)],
\end{align*}
where $[\cdot]$ is $1$ if the condition holds and $0$ otherwise. Each value is the smallest $\Phi$ on the subtree of $v$ for the state of $v$, without the penalty of $v$ itself when $v$ is FREE. The term $u(c)$ is the penalty of a child that stays undominated: a FREE child $c$ of a vertex $v\notin X$ has no neighbour in $X$, and it costs $P$ unless $\mathrm{pre}(c)$. The term $a(c)$ is the cheapest value of a child $c\notin X$ whose parent is not in $X$. In $\mathrm{IN}(v)$ no child is in $X$ and every child is dominated by $v$, so a FREE child costs no penalty. In $\mathrm{FREE}(v)$ no child is in $X$. In $\mathrm{DOM}(v)$ every child takes its cheapest state, of value $\min(\mathrm{IN}(c),a(c))$, and the term $\delta(v)$ is the additional cost that makes $v$ dominated: $\delta(v)=0$ if $\mathrm{pre}(v)$, or if the cheapest state of some child is IN, that is, $\mathrm{IN}(c)\le a(c)$; otherwise one child has to be moved from its cheapest state to IN, and $\delta(v)=\min_c(\mathrm{IN}(c)-a(c))$ is the smallest increase, attained by the \emph{forced child}; if $\neg\mathrm{pre}(v)$ and $v$ has no child with $\mathrm{IN}(c)<\infty$, in particular if $v$ is a leaf, then $\mathrm{DOM}(v)=\infty$. A root $r$ takes $\min(\mathrm{IN}(r),\mathrm{DOM}(r),\mathrm{FREE}(r)+u(r))$, and back-pointers recover $X$.
\paragraph{Example} Let $F$ be the path $\ell$--$p$--$r$--$q$ rooted at $r$, with neutral flags and $P=5$; the children of $r$ are $p$ and $q$, and $\ell$ is the child of $p$. For the leaves, $\mathrm{IN}(\ell)=\mathrm{IN}(q)=1$, $\mathrm{FREE}(\ell)=\mathrm{FREE}(q)=0$, $\mathrm{DOM}(\ell)=\mathrm{DOM}(q)=\infty$ and $a(\ell)=a(q)=\min(\infty,0+5)=5$. For $p$, $\mathrm{IN}(p)=1+\min(\infty,0)=1$, $\mathrm{FREE}(p)=a(\ell)=5$, and $\mathrm{DOM}(p)=\min(\mathrm{IN}(\ell),a(\ell))+\delta(p)=1+0=1$, because $\mathrm{IN}(\ell)=1\le a(\ell)=5$; hence $a(p)=\min(1,5+5)=1$. For the root, $\mathrm{IN}(r)=1+\min(\mathrm{DOM}(p),\mathrm{FREE}(p))+\min(\mathrm{DOM}(q),\mathrm{FREE}(q))=1+1+0=2$, $\mathrm{FREE}(r)=a(p)+a(q)=1+5=6$, and $\mathrm{DOM}(r)=\min(1,1)+\min(1,5)+\delta(r)=2+0=2$. The root takes $\min(2,2,6+5)=2$. With the state IN for $r$, the child $p$ takes DOM and its child $\ell$ takes IN, and $q$ takes FREE, which gives $X=\{r,\ell\}$; with the state DOM for $r$, both children take IN, which gives $X=\{p,q\}$. Both are minimum independent dominating sets of the path, and $i(F)=2$.
\begin{algorithm}[H]
\caption{\textsc{ConditionedForestIDS}$(F,\mathrm{in},\mathrm{pre},\mathrm{force},P)$}
\label{alg:forestdp}
\begin{algorithmic}[1]
\Require An induced forest $F$, flags, penalty $P>|V(F)|$
\Ensure A minimiser $X$ of $\Phi$
\For{every tree of $F$}
\State root it; compute a BFS order and the children lists
\For{$v$ in reverse BFS order} compute $\mathrm{IN}(v),\mathrm{DOM}(v),\mathrm{FREE}(v)$ and the forced child \EndFor
\State choose the state of the root; assign the states top-down by the recorded choices; add the IN vertices to $X$
\EndFor
\State \Return $X$
\end{algorithmic}
\end{algorithm}
With neutral flags ($\mathrm{in}\equiv$ true, $\mathrm{pre}\equiv\mathrm{force}\equiv$ false) the algorithm returns a minimum independent dominating set of $F$ (Lemma~\ref{lem:forestdp}). \textsc{ResolveLayer}$(S,L)$ fixes every vertex outside the induced forest $L$ from a set $S$, sets the flags accordingly (a vertex outside $L$, not in $S$, without a neighbour in $S$ outside $L$ and with exactly one selectable neighbour in $L$ forces that neighbour), solves $L$ by Algorithm~\ref{alg:forestdp} and completes the result by Algorithm~\ref{alg:complete}. \textsc{ForestLNS} applies \textsc{ResolveLayer} to every layer of $\mathcal L$, keeping a new set when it is not larger, for at most two passes and a work budget of $40(n+m)$.
\subsection{Base strategies}
\label{sec:base}
\paragraph{$c_1$: spanning-tree peeling} Round by round, on the residual graph $R$ (initially $G$), a maximum spanning forest of $R$ with edge weights $\deg_R(u)+\deg_R(v)$ is computed by Kruskal's algorithm on the edges bucket-sorted by weight, with a union-find structure using union by size and path halving~\cite{tarjan1975efficiency}; the forest is solved exactly by Algorithm~\ref{alg:forestdp}; a maximal $G$-independent subset of the forest optimum, larger residual degree first, is kept; the kept vertices and their neighbours are removed. A round on a residual graph with $n_R$ vertices and $m_R$ edges is charged $4(n_R+m_R)$ work units, and the rounds stop at a work budget of $40(n+m)$. Every pointer step of a find operation is charged to a second counter with the limit $320(n+m)$, tested after every edge; when it is exceeded, Kruskal's algorithm stops adding edges, the round is finished on the forest built so far, and it is the last round. The vertices left are completed by Algorithm~\ref{alg:complete}.
\paragraph{$c_2$--$c_8$} $c_2$ completes the endpoints of the NetworkX~\cite{hagberg2008exploring} minimum maximal matching; every unmatched vertex has all its neighbours matched, so the endpoints and the isolated vertices dominate $G$. $c_3$ is Algorithm~\ref{alg:complete} from the empty seed. $c_4$ solves the spanning forest in which every vertex points to the vertex of largest pair (degree, index) in its closed neighbourhood; these pairs strictly increase along the pointers, so they form a forest. $c_5$ (Min-to-Min) repeatedly takes the undominated vertex of smallest residual degree and selects the free vertex of its closed neighbourhood that dominates most undominated vertices. $c_6$ processes the undominated vertices by increasing degree, raises the dual variable of $v$ in the linear program $\min\sum_ux_u$, $\sum_{u\in N[v]}x_u\ge1$, until a free vertex of $N[v]$ becomes tight, and selects the tight free vertex of largest degree. $c_7$ and $c_8$ solve a BFS and a DFS spanning forest, rooted by decreasing degree. The optimum of a spanning forest dominates $G$ but need not be independent in $G$; Algorithm~\ref{alg:complete} repairs it.
\paragraph{$c_9$: induced-forest layers} Algorithm~\ref{alg:layers} splits every connected component into layers, each an induced forest, and solves the layers in several orders. The trees of the layer under construction are kept in a union-find structure with union by size and path halving. A pass over the remaining vertices is charged their number plus the sum of their degrees, within the budget $8(n+m)$, and every pointer step of a find operation is charged to a second counter with the limit $64(n+m)$, tested after every find; when either runs out, the layer under construction is closed with the vertices accepted so far, and the vertices not placed are left to the greedy completion.
\begin{algorithm}[H]
\caption{\textsc{ForestLayers}$(\mathrm{adj})$}
\label{alg:layers}
\begin{algorithmic}[1]
\Require Index graph; layering budget $8(n+m)$; find budget $64(n+m)$; at most $6$ orders per component
\Ensure An independent dominating set and the layers $\mathcal L$
\For{every connected component $C$}
\State $R\gets V(C)$ sorted by increasing degree; $t\gets0$
\While{$R\neq\emptyset$ and the budgets allow}
\State $L_t\gets\emptyset$
\For{$v\in R$} add $v$ to $L_t$ if its neighbours in $L_t$ lie in pairwise different trees of $L_t$ (union-find) \EndFor
\State $R\gets R\setminus L_t$; $t\gets t+1$
\EndWhile
\For{every order $\sigma$ of the layers (all of them if $t!\le6$, otherwise the natural and the reverse order and their rotations, at most $6$)}
\State $X\gets\emptyset$
\For{$L$ in the order $\sigma$} $X\gets X\cup\textsc{ConditionedForestIDS}(L\setminus(X\cup N(X)))$ with neutral flags \EndFor
\State complete $X$ greedily on the vertices still undominated; keep the smallest $X$
\EndFor
\EndFor
\end{algorithmic}
\end{algorithm}
\paragraph{$c_{10}$ and $c_{11}$} $c_{10}$ is \textsc{ResolveLayer} of the first layer of $\mathcal L$ with the rest fixed from the best of $c_1$--$c_9$, kept when it is not larger. $c_{11}$ peels a feedback vertex set (the \emph{core}) by the reductions of \textsc{Salvador}'s $c_{11}$ on a multigraph: a vertex of residual degree at most $1$ lies on no cycle and is removed; a vertex $v$ of residual degree $2$ with distinct neighbours $a,b$ is bypassed, replaced by an edge $a$--$b$; when both edges of a vertex of degree $2$ go to the same $b$, the vertex $b$ goes to the core; otherwise the vertex of largest residual degree goes to the core. The vertices outside the core induce a forest of $G$, which is solved by \textsc{ResolveLayer} for three choices on the core (the choice of the best of $c_1$--$c_{10}$, no core vertex, and the greedy solution of the core); the smallest set is kept.
\paragraph{$c_{12}$} $c_{12}$ is the dynamic minimum-degree greedy of \textsc{Esperanza}, which repeatedly selects a vertex of smallest residual degree and deletes its closed neighbourhood~\cite{caro1979new,wei1981lower}.
\paragraph{$c_{13}$: degree splitting} Algorithm~\ref{alg:split} replaces every vertex of degree larger than $k=\lfloor\sqrt n\rfloor$ by unconnected copies, each joined to at most $k$ of its neighbours, solves the copy graph and maps the solution back.
\begin{algorithm}[H]
\caption{\textsc{DegreeSplit}$(\mathrm{adj})$}
\label{alg:split}
\begin{algorithmic}[1]
\Require Index graph on $n$ vertices
\Ensure An independent dominating set of $G$
\State $k\gets\max(1,\lfloor\sqrt n\rfloor)$; $H\gets G$; $\mathrm{owner}(v)\gets v$
\For{$u\in V$ by decreasing degree (counting sort)}
\If{$\deg_H(u)>k$}
\State let $w_1,\dots,w_d$ be the neighbours of $u$ in $H$; remove $u$ from $H$
\For{$j=1,\dots,\lceil d/k\rceil$} add a node $u_j$ with $\mathrm{owner}(u_j)=u$, joined to $w_{(j-1)k+1},\dots,w_{\min(jk,d)}$ \EndFor
\EndIf
\EndFor
\For{each inner solver $A\in\{\textsc{Complete}(\emptyset),\textsc{MinToMin},\textsc{ForestLayers}\}$}
\State $S_H\gets A(H)$; $\mathrm{cnt}(v)\gets|\{x\in S_H:\mathrm{owner}(x)=v\}|$; $S_0\gets\{v:\mathrm{cnt}(v)>0\}$
\State $S_A\gets\textsc{Complete}(\mathrm{adj},S_0,\pi=\mathrm{cnt})$ \Comment{repair with pruning}
\EndFor
\State \Return the smallest $S_A$
\end{algorithmic}
\end{algorithm}
\subsection{Improvers and the weighted swap search}
\label{sec:improvers}
$c_{14}$ completes the union of $c_2$--$c_8$, discarding first the vertices chosen by fewer of them. $c_{17}$ (consensus forcing) runs three rounds: round $k$ takes the vertices chosen by at least a fraction $q_k\in\{1,0.9,0.75\}$ of the sets in the pool, keeps an independent subset of them (most votes first), removes them with their neighbours, solves the residual graph by the best of Algorithm~\ref{alg:complete}, Min-to-Min and Algorithm~\ref{alg:layers}, and adds the result to the pool.
Algorithm~\ref{alg:improve} is the local search used by $c_{15}$, $c_{16}$ and $c_{18}$. Its first phase is a descent: a \emph{move} at a vertex $u\notin S$ inserts $u$, removes the $k=|N(u)\cap S|$ neighbours of $u$ in $S$, and refills the vertices left undominated, which all lie in the neighbourhoods of the removed vertices, by the greedy of Algorithm~\ref{alg:complete} restricted to them; the move is kept when $S$ shrinks, which requires $k\ge2$. Its second phase is a weighted swap search on a set $S$ of fixed size $k$ that may leave vertices undominated and contain conflicting edges. With weights $w(v)\ge1$ on the vertices and $w(e)\ge1$ on the edges, it minimises
\[
\mathrm{cost}(S)=\sum_{v:\,N[v]\cap S=\emptyset}w(v)+\sum_{e\subseteq S}w(e),
\]
so that every vertex, not only an undominated one, may enter $S$. When $\mathrm{cost}(S)=0$, $S$ is an independent dominating set of size $k$; it is recorded and one vertex is removed to try $k-1$.
\begin{algorithm}[H]
\caption{\textsc{ImproveIDS}$(\mathrm{adj},S_0,B,\sigma)$}
\label{alg:improve}
\begin{algorithmic}[1]
\Require An independent dominating set $S_0$; work budget $W=\max(B(n+m),F)$; seed $\sigma$; lower bound $LB$
\Ensure An independent dominating set $S^*$ with $|S^*|\le|S_0|$
\State $S\gets$ descent from $S_0$ (moves at vertices with $k\ge2$, chained, within the budget); $S^*\gets S$
\For{segment $i=1,\dots,4$, each with a quarter of the remaining work and the weight cap $\theta_i\in(10,100,30,300)$ rotated by $\sigma$}
\State $S\gets S^*$ minus the vertex whose removal increases the cost least; all weights $\gets1$
\While{work remains and $|S^*|>LB$}
\State remove the vertex of $S$ of largest score among $50$ sampled ones (never the vertex added last)
\State take a random undominated vertex $v$; add the vertex of $N[v]$ of largest score allowed by configuration checking
\State add $1$ to the weight of every undominated vertex and of every conflicting edge; halve all weights when their mean exceeds $\theta_i$
\If{$\mathrm{cost}(S)=0$} $S^*\gets S$; remove from $S$ the vertex whose removal increases the cost least \EndIf
\EndWhile
\EndFor
\State \Return $S^*$ after a last descent
\end{algorithmic}
\end{algorithm}
The score of a vertex is the decrease of the cost when it changes side; configuration checking forbids a removed vertex to re-enter before one of its neighbours has changed side. All scores, the domination counts and the sets of violations are updated incrementally in time proportional to the degrees of the two-hop neighbourhood of the changed vertex, and every operation is charged to a work counter. The default budgets are $B=10$ for $c_{15}$, $5$ per round for $c_{16}$, $3$ per candidate and $30$ for the final search of $c_{18}$, with the constant floors $F=\min(2\cdot10^6,\,10(n+m)^2)$ and, for the final search, $F=\min(24\cdot10^6,\,100(n+m)^2)$; the seed is $20261031$.
\section{Correctness of the Algorithm}
\label{sec:correctness}
\begin{Lemma}[Repair and completion]
\label{lem:complete}
For every seed $P$, Algorithm~\ref{alg:complete} returns an independent dominating set of $G$, in $O(n+m+\max\pi)$ time.
\end{Lemma}
\begin{proof}
After the repair loop no vertex of $S$ has a neighbour in $S$: a vertex is examined with its current conflict count and is removed whenever it is positive, and removals only decrease the counts of the others, so a vertex that keeps a positive count when examined is removed, and a vertex examined with count $0$ keeps count $0$ because no vertex is added during the loop. In the completion loop a vertex is added only when it lies in $U$, i.e.\ when no vertex of its closed neighbourhood is in $S$, so $S$ stays independent, and the loop ends when $U=\emptyset$, i.e.\ when every vertex is dominated. The counting sorts cost $O(n+\Delta+\max\pi)$ and every vertex leaves $U$ once, with one scan of its neighbourhood, so the bucket queue costs $O(n+m)$.
\end{proof}
\begin{Lemma}[Exact conditioned forest solver]
\label{lem:forestdp}
Algorithm~\ref{alg:forestdp} returns a minimiser of $\Phi$ in $O(\sum_{v\in V(F)}\deg_G(v))$ time. With neutral flags and $P>|V(F)|$, the minimiser is a minimum independent dominating set of $F$.
\end{Lemma}
\begin{proof}
For a rooted subtree $T_v$, $\mathrm{IN}(v)$, $\mathrm{DOM}(v)$ and $\mathrm{FREE}(v)$ are the minimum of the part of $\Phi$ carried by $T_v$ over independent sets $X\cap T_v$ in which $v$ is selected, dominated by a child or from outside, or not dominated by its children, respectively; the penalty of $v$ itself in the state FREE is paid by its parent ($u(c)$) unless the parent is selected, and the penalty of a forced unselected vertex is added in the states DOM and FREE. The recurrences enumerate exactly these cases: a selected vertex excludes selected children and dominates them; a dominated vertex needs one selected child unless it is pre-dominated, and the cheapest such child is forced when none is chosen freely; a vertex with an unselected parent pays $u(c)$ in the state FREE. Induction over the reverse BFS order gives the minimum at the root, and the top-down reconstruction follows the recorded minimising choices. Each vertex scans its neighbourhood a constant number of times. With neutral flags, every independent dominating set $X$ of $F$ has $\Phi(X)=|X|\le|V(F)|
k\}$. The copy graph $H$ has maximum degree at most $k$, exactly $m$ edges, every edge of $H$ joins two nodes whose owners are adjacent in $G$, every edge of $G$ corresponds to exactly one edge of $H$, two copies of the same vertex are never adjacent, and $|V(H)|=n-|B|+\sum_{v\in B}\lceil\deg_G(v)/k\rceil\le n+2m/k$. It is built in $O(n+m)$ expected time.
\end{Lemma}
\begin{proof}
Splitting $u$ replaces every edge $uw$ of $H$ by one edge $u_jw$ and changes no other degree; hence when $u$ is examined $\deg_H(u)=\deg_G(u)$, the copies of $u$ get at most $k$ neighbours each, and every vertex that is not split keeps its degree, at most $k$. Edges are moved one to one, so $H$ has $m$ edges, each between nodes with adjacent owners, and the copies of $u$ are joined only to neighbours of $u$. Since $\lceil d/k\rceil\le d/k+1$, $|V(H)|\le n+\sum_{v\in B}\deg_G(v)/k\le n+2m/k$. Every edge is moved at most twice, once for each endpoint.
\end{proof}
\begin{Theorem}[Running time]
\label{thm:runtime}
For the default parameters, Algorithm~\ref{alg:main} runs in $O(n+m)$ expected time.
\end{Theorem}
\begin{proof}
The conversion, the components, the lower bound $LB$ and the verifications are linear. No step uses a comparison sort: every sort is a counting sort on integer keys at most $n+m$. $c_2$ uses the linear NetworkX matching; $c_3$--$c_8$ and $c_{12}$ are single passes with bucket queues, $O(n+m)$, using Lemmas~\ref{lem:complete} and~\ref{lem:forestdp}. $c_1$ and $c_9$ run Kruskal's algorithm and the layering with a union-find structure with union by size and path halving~\cite{tarjan1975efficiency}. Apart from the pointer steps of the find operations, the work of a round of $c_1$ and of a pass of the layering is within a constant factor of the units charged to the budgets $40(n+m)$ and $8(n+m)$. The pointer steps are charged to the second counters, with the limits $320(n+m)$ and $64(n+m)$; a tree of the structure with a vertex at depth $h$ has at least $2^h$ vertices, so one find takes at most $\log_2n$ pointer steps, and the counters are tested after at most two finds, so they are exceeded by at most $2\log_2n$. Hence $c_1$ and the layering take $O(n+m)$ time in the worst case, and $c_9$ solves at most $6$ orders per component, each $O(n+m)$. $c_{10}$ and $c_{11}$ are $O(n+m)$: every rule of the core peeling removes one vertex with $O(\deg)$ expected dictionary operations, and the bypass does not change degrees. $c_{13}$ is linear by Lemma~\ref{lem:copy}, since the inner solvers and the three repairs are linear in $|V(H)|+m=O(n+m)$. The improvers are bounded by work counters: every scan, update, insertion, removal and undo of Algorithm~\ref{alg:improve} and of \textsc{ForestLNS} is charged to a counter that stops the search at $\max(B(n+m),F)$ units, with fixed $B$ and constant $F$, and a single move exceeds the limit by at most $O(n+m)$. $c_{17}$ runs three rounds of linear work. There are at most eighteen distinct candidates, so the total is $O(n+m)$.
\end{proof}
\section{Proved Bounds}
\label{sec:ratio}
\begin{Lemma}[Maximal-set bound]
\label{lem:mis}
Every maximal independent set $M$ of a graph $G$ of maximum degree $\Delta\ge1$ satisfies $n/(\Delta+1)\le i(G)\le|M|\le\Delta\,i(G)$.
\end{Lemma}
\begin{proof}
A minimum independent dominating set $D$ satisfies $V=\bigcup_{d\in D}N[d]$, so $n\le(\Delta+1)|D|$. $M$ is an independent dominating set, so $i(G)\le|M|$. For $d\in D$, $|M\cap N[d]|=1$ if $d\in M$, and $M\cap N[d]\subseteq N(d)$ has at most $\Delta$ vertices otherwise; since $M\subseteq\bigcup_{d\in D}N[d]$, $|M|\le\Delta|D|$.
\end{proof}
\begin{Corollary}[Bounded degree]
\label{cor:delta}
For every graph $G$, the output $S$ of Algorithm~\ref{alg:main} satisfies $|S|\le\max(1,\Delta)\,i(G)$; in particular the ratio is at most $\Delta$ on every graph with an edge.
\end{Corollary}
\begin{proof}
Isolated vertices belong to $S$ and to every independent dominating set, and on every other component $S$ is a maximal independent set (Theorem~\ref{thm:correctness}), so Lemma~\ref{lem:mis} applies componentwise and the bounds add up.
\end{proof}
\begin{Lemma}[Certified lower bound]
\label{lem:lb}
For every graph $G$ with components $C$, $i(G)\ge LB=\sum_C\lceil n_C/(\Delta_C+1)\rceil$. If the output has at most $LB$ vertices, it is optimal.
\end{Lemma}
\begin{proof}
An independent dominating set of $G$ restricts to one of every component, and Lemma~\ref{lem:mis} gives $i(C)\ge n_C/(\Delta_C+1)$, an integer bound after rounding up.
\end{proof}
\begin{Theorem}[Forests]
\label{thm:forest}
If $G$ is a forest, the output of Algorithm~\ref{alg:main} is a minimum independent dominating set.
\end{Theorem}
\begin{proof}
On a forest, the core of $c_{11}$ is empty. Indeed, the residual multigraph stays a forest: removing a vertex keeps it one, and bypassing a vertex $v$ of degree $2$ with neighbours $a\neq b$ contracts an edge and creates no parallel edge, because $a$ and $b$ are not adjacent (otherwise $a$, $v$, $b$ would lie on a cycle). So no vertex of degree $2$ has both edges to the same vertex, and as long as vertices remain one of them has degree at most $1$; the rules that send a vertex to the core never apply. Hence $c_{11}$ is \textsc{ResolveLayer} on the forest $G$ with no vertex fixed, that is, Algorithm~\ref{alg:forestdp} with neutral flags and $P=n+1$, which returns a minimum independent dominating set of $G$ by Lemma~\ref{lem:forestdp}, followed by Algorithm~\ref{alg:complete}, which removes a vertex only when it has a neighbour in the set and adds a vertex only when it is undominated, and so leaves an independent dominating set unchanged. Every candidate after $c_{11}$ is either a strategy output or the result of a search that never returns a larger set, and $c_{18}$ is no larger than any of them, so $|c_{18}|\le|c_{11}|=i(G)$.
\end{proof}
The next theorem is the counterpart of the $O(\sqrt n)$ theorem of \textsc{Esperanza}~\cite{Vega26}, which gives the ratio $2\sqrt n$ for maximum independent set on graphs with $\Delta\le\sqrt n$; for MIDS the bound is $\Delta$ itself.
\begin{Theorem}[Ratio $\sqrt n$ on three classes]
\label{thm:sqrt}
Let $S$ be the output of Algorithm~\ref{alg:main} on a graph $G$ with $n$ vertices. If at least one of the following conditions holds, then $|S|/i(G)\le\sqrt n$:
\begin{enumerate}
\item[(a)] $\Delta\le\sqrt n$, and then $|S|/i(G)\le\max(1,\Delta)$;
\item[(b)] $i(G)\ge\sqrt n$;
\item[(c)] $\alpha(G)\le\sqrt n\;i(G)$.
\end{enumerate}
\end{Theorem}
\begin{proof}
(a) is Corollary~\ref{cor:delta}. (b) $|S|\le n$, so $|S|/i(G)\le n/\sqrt n$. (c) $S$ is independent, so $|S|\le\alpha(G)\le\sqrt n\,i(G)$.
\end{proof}
The degree-splitting strategy $c_{13}$ extends condition (a) to graphs with vertices of degree larger than $\sqrt n$. For $k=\max(1,\lfloor\sqrt n\rfloor)$ and $B=\{v:\deg_G(v)>k\}$ define the \emph{splitting excess}
\[
s(G)=\sum_{v\in B}\Bigl(\Bigl\lceil\frac{\deg_G(v)}{k}\Bigr\rceil-1\Bigr)\ \le\ \sum_{v\in B}\frac{\deg_G(v)}{k}\ \le\ \frac{2m}{k}.
\]
\begin{Lemma}[Lifting]
\label{lem:lift}
For the copy graph $H$ of Algorithm~\ref{alg:split}, $i(H)\le i(G)+s(G)$.
\end{Lemma}
\begin{proof}
Let $D$ be a minimum independent dominating set of $G$, and let $L$ be the set of nodes of $H$ whose owner lies in $D$; $|L|=\sum_{u\in D}\lceil\deg_G(u)/k\rceil$ over split $u$, plus one per unsplit $u$. $L$ is independent in $H$, since an edge of $H$ joins nodes with adjacent owners (Lemma~\ref{lem:copy}) and $D$ is independent. Let $z$ be a node of $H$ with owner $w\notin D$. The vertex $w$ has a neighbour $u\in D$, and the edge $uw$ of $G$ corresponds to exactly one edge of $H$, between a node owned by $u$, which lies in $L$, and a node owned by $w$. If $w$ is not split, that node is $z$, so $z$ is dominated by $L$; if $w$ is split, at least one of its $\lceil\deg_G(w)/k\rceil$ copies is dominated. Completing $L$ greedily to a maximal independent set of $H$ adds only undominated nodes, at most $\lceil\deg_G(w)/k\rceil-1$ for every split $w\notin D$. Hence $i(H)\le|D|+\sum_{u\in D\cap B}(\lceil\deg_G(u)/k\rceil-1)+\sum_{w\in B\setminus D}(\lceil\deg_G(w)/k\rceil-1)=i(G)+s(G)$.
\end{proof}
\begin{Lemma}[Decoding]
\label{lem:decode-split}
For every independent dominating set $S_H$ of $H$, the set $S_0=\{\mathrm{owner}(x):x\in S_H\}$ is a dominating set of $G$ with $|S_0|\le|S_H|$. If $S_0$ is independent in $G$, then $\textsc{Complete}(\mathrm{adj},S_0,\pi)=S_0$.
\end{Lemma}
\begin{proof}
$|S_0|\le|S_H|$ because the owner map is a function. Let $w\in V$. If $w$ is not split, the node $w$ of $H$ is in $S_H$, so $w\in S_0$, or it has a neighbour $x\in S_H$, whose owner is a neighbour of $w$ in $G$. If $w$ is split, its first copy has at least one neighbour, and the same argument applies to that copy. If $S_0$ is independent, the repair loop of Algorithm~\ref{alg:complete} removes nothing, and $U=\emptyset$ because $S_0$ dominates $G$, so nothing is added.
\end{proof}
\begin{Theorem}[Degree splitting]
\label{thm:split}
Let $k=\max(1,\lfloor\sqrt n\rfloor)$. For each inner solver of Algorithm~\ref{alg:split}, the decoded set $S_0$ is a dominating set of $G$ with
\[
|S_0|\ \le\ k\,\bigl(i(G)+s(G)\bigr).
\]
If $S_0$ is independent in $G$ for one of the inner solvers, then the output $S$ of Algorithm~\ref{alg:main} satisfies $|S|\le k\,(i(G)+s(G))$, so $|S|/i(G)\le\lfloor\sqrt n\rfloor\,(1+s(G)/i(G))$; in particular $|S|/i(G)\le2\sqrt n$ when $s(G)\le i(G)$.
\end{Theorem}
\begin{proof}
Every inner solver returns a maximal independent set $S_H$ of $H$ (Lemma~\ref{lem:complete} and Theorem~\ref{thm:correctness}). $H$ has maximum degree at most $k$ by Lemma~\ref{lem:copy}, so Lemma~\ref{lem:mis}, applied componentwise in $H$ with $\max(1,\Delta(H))\le k$, gives $|S_H|\le k\,i(H)$, and Lemma~\ref{lem:lift} gives $i(H)\le i(G)+s(G)$. Lemma~\ref{lem:decode-split} gives $|S_0|\le|S_H|$ and domination. Strategy $c_{13}$ applies Algorithm~\ref{alg:complete} to $S_0$. If $S_0$ is independent, Algorithm~\ref{alg:complete} returns $S_0$ itself (Lemma~\ref{lem:decode-split}), so the candidate $c_{13}$ has at most $|S_0|$ vertices, and the output is no larger than $c_{13}$. If $S_0$ is not independent, Algorithm~\ref{alg:complete} removes vertices of $S_0$ and can add other vertices, and the bound is proved for $S_0$ only.
\end{proof}
On a graph with $\Delta\le k$ no vertex is split, $s(G)=0$, $H=G$, and Theorem~\ref{thm:split} reduces to Theorem~\ref{thm:sqrt}(a). On a star $K_{1,n-1}$, $s(G)=\lceil(n-1)/k\rceil-1$, the copy graph is a disjoint union of $\lceil(n-1)/k\rceil$ stars, and every maximal independent set of $H$ that contains the copies of the centre decodes to the optimum $\{\text{centre}\}$. The bound of Theorem~\ref{thm:split} on $S_0$ holds on every graph, whereas the bound on the output requires the independence of $S_0$.
\paragraph{Worst cases of the splitting excess} The excess $s(G)$ is largest on dense graphs; the next two propositions show that the graphs on which it is largest are graphs on which the output is optimal.
\begin{Proposition}[Splitting excess]
\label{prop:sworst}
Let $G$ be a graph on $n\ge3$ vertices with $m$ edges, $k=\lfloor\sqrt n\rfloor$ and $B=\{v:\deg(v)>k\}$.
\begin{enumerate}
\item[(i)] $s(G)=0$ if and only if $\Delta\le k$; then no vertex is split, $H=G$, and the scan of Algorithm~\ref{alg:split} ends at its first vertex.
\item[(ii)] $s(G)\le\sum_{v\in B}\frac{\deg(v)-1}{k}\le\min\Bigl\{\frac{2m-|B|}{k},\,\frac{|B|\,(n-2)}{k}\Bigr\}\le|B|\,(\sqrt n+1)\le n\,(\sqrt n+1)$.
\item[(iii)] The complete graph maximises the excess: $s(G)\le s(K_n)=n\bigl(\lceil(n-1)/k\rceil-1\bigr)$, and $s(K_n)\ge n^{3/2}-n-\sqrt n$.
\item[(iv)] For the complete bipartite graph $K_{a,b}$ with $a\le b$ and $a+b=n$, $s(K_{a,b})=a\,(\lceil b/k\rceil-1)+b\,(\lceil a/k\rceil-1)$; a term vanishes when its degree is at most $k$. In particular $s(K_{n/2,n/2})=n\,(\lceil n/(2k)\rceil-1)$ for even $n$, and $s(K_{1,n-1})=\lceil(n-1)/k\rceil-1$.
\end{enumerate}
\end{Proposition}
\begin{proof}
(i) $\lceil d/k\rceil-1=0$ exactly when $d\le k$. The vertices are scanned by decreasing degree and splitting changes no other degree (Lemma~\ref{lem:copy}), so when the first vertex has degree $\Delta\le k$ no vertex is split. (ii) For every integer $d\ge1$, $\lceil d/k\rceil\le(d-1)/k+1$. Summing over $B$ gives the first inequality, and $\sum_{v\in B}\deg(v)\le2m$ and $\deg(v)\le n-1$ give the second. Since $k>\sqrt n-1>0$ and $n-2\sqrt n\ge k$ for $n\ge3$, so every vertex lies in $B$ and attains the maximum. Moreover $\lceil(n-1)/k\rceil\ge(n-1)/\sqrt n=\sqrt n-1/\sqrt n$, which gives the lower bound. (iv) The $a$ vertices of one side have degree $b$ and the $b$ vertices of the other side have degree $a$.
\end{proof}
\begin{Proposition}[Rigid dense families]
\label{prop:complete}
If every connected component of $G$ is a complete multipartite graph (in particular a complete graph, a complete bipartite graph or a star), a crown graph with $t\ge3$ vertices on each side (the complete bipartite graph $K_{t,t}$ minus a perfect matching), a wheel or a double star, the output of Algorithm~\ref{alg:main} is a minimum independent dominating set.
\end{Proposition}
\begin{proof}
Gains are local to the components, and whenever the greedy $c_3$ selects a vertex of a component $C$, that vertex has the largest gain $|N[v]\cap U|$ among the undominated vertices of $C$; we show that $c_3$ is optimal on every such component, and the output is no larger than $c_3$ (proof of Theorem~\ref{thm:forest}). \emph{Complete multipartite} $C$ with parts $P_1,\dots,P_r$: a vertex of $P_j$ has gain $|C|-|P_j|+1$, so the first vertex selected lies in a smallest part $P$; it dominates every other part, the other vertices of $P$ are undominated, have no undominated neighbour and are all selected, so $c_3\cap C=P$. An independent dominating set that contains a vertex of a part contains no vertex of the other parts, hence all of that part to dominate it, so $i(C)=\min_j|P_j|$. \emph{Crown} with sides $\{a_1,\dots,a_t\}$, $\{b_1,\dots,b_t\}$ and $a_i b_j\in E$ iff $i\neq j$: all gains are $t$, so $c_3$ first selects, say, $a_1$, which dominates every $b_j$ with $j\neq1$; then $b_1$ has gain $t$ and every $a_i$, $i\ge2$, has gain $20$, the random graph $G(n,c/n)$ satisfies $s(G)=0$ with probability tending to $1$ as $n\to\infty$.
\item[(e)] \emph{Few hubs.} $s(K_{1,n-1})=s(W_n)=\lceil(n-1)/k\rceil-1$ for the star and the wheel, and the double star with $a$ and $b$ leaves has $s=(\lceil(a+1)/k\rceil-1)+(\lceil(b+1)/k\rceil-1)$.
\item[(f)] \emph{Dense graphs.} If the minimum degree satisfies $\delta(G)>k$, then $s(G)\ge n(\lceil\delta(G)/k\rceil-1)$. The complete multipartite graph with parts of sizes $n_1,\dots,n_r$ has $s=\sum_jn_j(\lceil(n-n_j)/k\rceil-1)$, and the crown graph on $n=2t$ vertices has $s=n(\lceil(t-1)/k\rceil-1)$.
\end{enumerate}
\end{Proposition}
\begin{proof}
(a) $\lfloor\sqrt n\rfloor\ge D$ if and only if $n\ge D^2$, and then $\Delta\le k$, so $s(G)=0$ by Proposition~\ref{prop:sworst}(i). The graph $h(H)$ has $|V(H)|+6|E(H)|$ vertices and maximum degree $\max(\Delta(H),3)$; $Q_q$ has $2^q$ vertices and degree $q\le2^{q/2}$ for $q\ge4$; grids have degree at most $4$. (b) A vertex $(v,x)$ is adjacent only to vertices of the $d$ neighbouring blocks, each with $s_b$ vertices; $ds_b\le\sqrt{Ns_b}$ if and only if $N\ge d^2s_b$. (c) Proposition~\ref{prop:sworst}(ii) with $m\le3n-6$ for planar and $m\le2n-4$ for bipartite planar graphs; $n/\lfloor\sqrt n\rfloor\sqrt n$, a fixed vertex has degree at least $t$ with probability at most $\binom{n-1}{t}(c/n)^t\le(ec/t)^t\le(ec/\sqrt n)^{\sqrt n}$ once $t>ec$, so the probability that some vertex has degree larger than $k$ is at most $n(ec/\sqrt n)^{\sqrt n}\to0$, and then $s(G)=0$. (e) The hubs have degrees $n-1$, $a+1$ and $b+1$, every other vertex has degree at most $3\le k$ for $n\ge9$, and the formula of $s$ applies. (f) Every vertex lies in $B$ and $\lceil\deg(v)/k\rceil\ge\lceil\delta(G)/k\rceil$; a vertex of the part $j$ has degree $n-n_j$, and every vertex of the crown has degree $t-1$.
\end{proof}
\begin{table}[H]
\centering
\scriptsize
\caption{The splitting excess $s(G)$ ($k=\lfloor\sqrt n\rfloor$) and the output on graph families. ``Hardness'' cites the hardness of MIDS on the family, or of the vertex cover problem it encodes; ``Output'' is the guarantee proved for Algorithm~\ref{alg:main}.}
\label{tab:sfamilies}
\resizebox{\textwidth}{!}{%
\begin{tabular}{llllll}
\toprule
Family & Hardness & $\Delta$ & $s(G)$ & $i(G)$ & Output \\
\midrule
cubic, $n\in\{4,6,8\}$ & --- & $3$ & $n$ & $\ge n/4$ & ratio $\le2$ \\
cubic, $n\ge10$ & APX-hard~\cite{bazgan2020domination} & $3$ & $0$ & $\ge n/4$ & ratio $\le2$ \\
cubic planar, $n\ge10$ & NP-hard~\cite{manlove1999algorithmic} & $3$ & $0$ & $\ge n/4$ & ratio $\le2$ \\
cubic planar bipartite, $n\ge10$ & NP-complete~\cite{loverov2020np} & $3$ & $0$ & $\ge n/4$ & ratio $\le2$ \\
maximum degree $\le3$ & NP-hard within $1+\frac1{680}$~\cite{chlebik2008approximation} & $\le3$ & $\le8$; $0$ for $n\ge9$ & $\ge n/4$ & ratio $\le3$ \\
maximum degree $\le B$, bipartite or not, $n\ge B^2$ & NP-hard within $\delta B$~\cite{chlebik2008approximation} & $\le B$ & $0$ & $\ge n/(B+1)$ & ratio $\le B$ \\
SC-IDS of degree $B$, $n\ge B^2$ & reduction of~\cite{chlebik2008approximation} & $B$ & $0$ & $\mathrm{sc}+|\mathcal S|$ & ratio $\le B$ \\
VC-IDS $h(H)$, $\Delta(H)\le D$, $|V(h(H))|\ge\max(D,3)^2$ & vertex cover: UG-hard~\cite{khot2008vertex,austrin2011inapproximability} & $\max(D,3)$ & $0$ & $\tau(H)+2|E(H)|$ & ratio $\le\max(D,3)$ \\
Khot--Regev YES graphs, $N\ge d^2s_b$ & vertex cover: UG-hard~\cite{khot2008vertex} & $\le ds_b$ & $0$ & --- & ratio $\le ds_b$ \\
Khot--Regev YES graphs, any $N$ & vertex cover: UG-hard~\cite{khot2008vertex} & $\le ds_b$ & $\le n(\lceil ds_b/k\rceil-1)$ & --- & ratio $\le ds_b$ \\
planar, $n\ge400$ & NP-hard~\cite{manlove1999algorithmic} & unbounded & $<2\sqrt n+19$; $\ge2\sqrt n-3$ for some graphs & --- & --- \\
bipartite planar, $n\ge400$ & NP-hard~\cite{loverov2020np} & unbounded & $<2\sqrt n+12$; $\ge2\sqrt n-3$ for some graphs & --- & --- \\
circle graphs & not within $n^{\varepsilon}$, $\varepsilon<1$~\cite{damian1999hardness} & unbounded & up to $s(K_n)$ (maximum) & --- & --- \\
$m\le cn$ & --- & unbounded & $\le2c(\sqrt n+2)$ & --- & --- \\
$G(n,c/n)$ & --- & $\le k$ w.h.p. & $0$ w.h.p. & --- & ratio $\le\Delta$ \\
grids, $n\ge16$; hypercubes $Q_q$, $q\ge4$ & --- & $\le4$; $q$ & $0$ & --- & ratio $\le\Delta$ \\
star $K_{1,n-1}$, wheel $W_n$ & --- & $n-1$ & $\lceil(n-1)/k\rceil-1$ & $1$ & optimal \\
double star ($a\ge b$ leaves) & --- & $a+1$ & $\sum_{h\in\{a,b\}}(\lceil(h+1)/k\rceil-1)$ & $1+b$ & optimal \\
complete graph $K_n$ & --- & $n-1$ & $n(\lceil(n-1)/k\rceil-1)$ (maximum) & $1$ & optimal \\
complete bipartite $K_{a,b}$, $a\le b$ & --- & $b$ & $a(\lceil b/k\rceil-1)+b(\lceil a/k\rceil-1)$ & $\min(a,b)$ & optimal \\
complete multipartite & --- & $n-\min_jn_j$ & $\sum_jn_j(\lceil(n-n_j)/k\rceil-1)$ & $\min_jn_j$ & optimal \\
crown graph, $n=2t$ & --- & $t-1$ & $n(\lceil(t-1)/k\rceil-1)$ & $2$ & optimal \\
minimum degree $\delta>k$ & --- & $\ge\delta$ & $\ge n(\lceil\delta/k\rceil-1)$ & --- & --- \\
\bottomrule
\end{tabular}%
}
\end{table}
By Proposition~\ref{prop:families}(a), on every family of bounded degree $D$ on which MIDS is NP-hard or NP-hard to approximate, and on the VC-IDS graphs that encode UG-hard vertex cover instances of bounded degree, the splitting excess vanishes for $n\ge D^2$: strategy $c_{13}$ then solves $G$ itself, and Theorem~\ref{thm:split} gives the ratio $\lfloor\sqrt n\rfloor$, weaker than the ratio $\Delta$ of Corollary~\ref{cor:delta}. The excess is positive only on graphs with vertices of degree larger than $\sqrt n$; it is of order at most $\sqrt n$ on graphs with a constant number of such vertices or with $O(n)$ edges, and of order $n^{3/2}$ on dense graphs, among them the complete, complete multipartite and crown graphs, on which the output is optimal (Proposition~\ref{prop:complete}). On all $55$ instances of Section~\ref{sec:ugcexp}, $\Delta\le\lfloor\sqrt n\rfloor$ (Table~\ref{tab:ugc}: $n\ge106$ and $\Delta\le6$ for SC-IDS, $n\ge500$ and $\Delta\le5$ for the regular VC-IDS graphs, $n\ge48\,172$ and $\Delta=64$ for the VC-IDS graphs of Khot--Regev instances), so $s=0$ on all of them.
\paragraph{Cubic graphs} MIDS is APX-hard on cubic graphs~\cite{bazgan2020domination} and NP-hard on cubic planar~\cite{manlove1999algorithmic} and cubic planar bipartite graphs~\cite{loverov2020np}. On these graphs the splitting excess is bounded by an absolute constant, and it vanishes from ten vertices on.
\begin{Proposition}[Splitting excess on cubic and bounded-degree graphs]
\label{prop:cubic}
Let $k=\max(1,\lfloor\sqrt n\rfloor)$.
\begin{enumerate}
\item[(i)] If $G$ is cubic, then $s(G)=n$ for $n\in\{4,6,8\}$ and $s(G)=0$ for every $n\ge10$; hence $s(G)\le8$ for every cubic graph.
\item[(ii)] If $\Delta(G)\le3$, then $s(G)\le8$, and $s(G)=0$ for every $n\ge9$.
\item[(iii)] If $\Delta(G)\le D$ for an integer $D\ge2$, then $s(G)k$ and contributes $\lceil3/2\rceil-1=1$, so $s(G)=n\le8$. For even $n\ge10$, $k\ge3=\Delta$, so $s(G)=0$ by Proposition~\ref{prop:sworst}(i). (ii) For $n\le3$, $k=1$, the degrees are at most $2$, and every vertex contributes at most $\lceil2/1\rceil-1=1$, so $s(G)\le3$. For $4\le n\le8$, $k=2$, a vertex of degree $3$ contributes $1$ and a vertex of degree at most $2$ contributes $0$, so $s(G)\le n\le8$. For $n\ge9$, $k\ge3\ge\Delta$ and $s(G)=0$. (iii) For $n\ge D^2$, $k\ge D\ge\Delta$ and $s(G)=0$. For $nk\}$ and $b=|B|$.
\begin{enumerate}
\item[(i)] If $n\ge36$, then $b<2n/(k-5)$ and $s(G)<2n/k+10n/(k(k-5))$; for $n\ge400$, $s(G)<2\sqrt n+19$.
\item[(ii)] If $G$ is bipartite and $n\ge16$, then $b<2n/(k-3)$ and $s(G)<2n/k+6n/(k(k-3))$; for $n\ge400$, $s(G)<2\sqrt n+12$.
\item[(iii)] For every $n\ge16$, the planar bipartite graph $K_{2,n-2}$ satisfies $s(K_{2,n-2})=2(\lceil(n-2)/k\rceil-1)\ge2\sqrt n-3$, and the output of Algorithm~\ref{alg:main} on it is optimal.
\end{enumerate}
\end{Proposition}
\begin{proof}
Let $R=V\setminus B$, let $e_B$ be the number of edges with both ends in $B$, $e_{BR}$ the number of edges between $B$ and $R$, and $D=\sum_{v\in B}\deg(v)=2e_B+e_{BR}$. The subgraph of the edges between $B$ and $R$ is bipartite and planar, so $e_{BR}<2n$ (a bipartite planar graph on $p\ge3$ vertices has at most $2p-4$ edges, and on $p\le2$ vertices at most $1$). (i) $G[B]$ is planar, so $e_B\le3b$ and $D<6b+2n$; every vertex of $B$ has degree at least $k+1$, so $b(k+1)\le D<6b+2n$, that is $b(k-5)<2n$, and $k\ge6$ for $n\ge36$. By Proposition~\ref{prop:sworst}(ii), $s(G)\le(D-b)/k<(5b+2n)/k<2n/k+10n/(k(k-5))$. For $n\ge400$, $k\ge20$, so $k-5\ge3k/4$, and $n<(k+1)^2$ gives $n/k^2<(21/20)^2<1.11$; hence $10n/(k(k-5))\le\frac{40}{3}\,n/k^2<14.8$, and $n/k<\sqrt n+2$ (proof of Proposition~\ref{prop:families}(c)) gives $s(G)<2\sqrt n+4+14.8<2\sqrt n+19$. (ii) $G[B]$ is bipartite planar, so $e_B\le2b$, $D<4b+2n$, $b(k-3)<2n$ with $k\ge4$ for $n\ge16$, and $s(G)<(3b+2n)/k<2n/k+6n/(k(k-3))$. For $n\ge400$, $k-3\ge17k/20$, so $6n/(k(k-3))\le\frac{120}{17}\,n/k^2<7.9$ and $s(G)<2\sqrt n+4+7.9<2\sqrt n+12$. (iii) $K_{2,n-2}$ is planar and bipartite. Its two vertices of degree $n-2>\sqrt n\ge k$ form $B$, and the other vertices have degree $2\le k$, so $s=2(\lceil(n-2)/k\rceil-1)\ge2(n-2)/\sqrt n-2=2\sqrt n-2-4/\sqrt n\ge2\sqrt n-3$ for $n\ge16$. The output is optimal by Proposition~\ref{prop:complete}.
\end{proof}
\paragraph{Circle graphs} A circle graph is the intersection graph of a set of chords of a circle; MIDS is NP-complete on circle graphs and, unless $\mathrm{P}=\mathrm{NP}$, not approximable within $n^{\varepsilon}$ for any $\varepsilon<1$~\cite{damian1999hardness}. A chord model of $n$ chords has $2n$ distinct endpoints, which we number $1,\dots,2n$ around the circle from a point that is not an endpoint, and we write the chord of $v$ as $(a_v,b_v)$ with $a_v0$ it is NP-hard to approximate Minimum Vertex Cover within $2-\varepsilon_0$. If for some fixed $\varepsilon_0>0$ the output $D$ of Algorithm~\ref{alg:main} satisfies $|D|\le i(h(H))+(1-\varepsilon_0)\,\tau(H)$ for every graph $H$ without isolated vertices, then $\mathrm{P}=\mathrm{NP}$. The assumption holds if UGC holds~\cite{khot2008vertex}, and in particular if the theorem reported in~\cite{openai2026ugc} holds; without any assumption, such a bound would refute UGC unless $\mathrm{P}=\mathrm{NP}$.
\end{Theorem}
\begin{proof}
Isolated vertices belong to no minimum vertex cover and can be removed from $H$. $h(H)$ has polynomial size, Algorithm~\ref{alg:main} runs in polynomial time, and by Lemma~\ref{lem:decode} and Proposition~\ref{prop:vcids} the decoded cover satisfies $|C_D|\le|D|-2m_H\le\tau(H)+(1-\varepsilon_0)\tau(H)=(2-\varepsilon_0)\tau(H)$. Under the assumption this solves an NP-hard problem in polynomial time. The theorem of Khot and Regev~\cite{khot2008vertex} derives the assumption from UGC.
\end{proof}
\paragraph{Bounded degree} Austrin, Khot and Safra proved that, assuming UGC, Minimum Vertex Cover on graphs of maximum degree $d$ is hard to approximate within $2-(2+o_d(1))\log\log d/\log d$~\cite{austrin2011inapproximability}. Since $h(H)$ has maximum degree $\max(\Delta(H),3)$, the VC-IDS reduction transfers this bound to MIDS instances of bounded degree.
\begin{Corollary}[Bounded-degree instances]
\label{cor:aks}
Assume UGC and $\mathrm{P}\neq\mathrm{NP}$. For every $\delta>0$ there is $d_0$ such that for every $d\ge d_0$ and every polynomial-time algorithm $\mathcal A$ that returns independent dominating sets, in particular Algorithm~\ref{alg:main}, there is a graph $H$ of maximum degree at most $d$ without isolated vertices with
\[
|\mathcal A(h(H))|\ >\ i(h(H))+\Bigl(1-(2+\delta)\frac{\log\log d}{\log d}\Bigr)\tau(H),
\]
and $h(H)$ has maximum degree at most $\max(d,3)$.
\end{Corollary}
\begin{proof}
Write the factor of~\cite{austrin2011inapproximability} as $2-(2+\varepsilon_d)\log\log d/\log d$ with $\varepsilon_d\to0$, and choose $d_0$ with $\varepsilon_d<\delta$ for $d\ge d_0$. If the inequality failed for every such $H$, Lemma~\ref{lem:decode} and Proposition~\ref{prop:vcids} would give a polynomial-time vertex cover algorithm with ratio at most $2-(2+\delta)\log\log d/\log d$, a smaller factor, on all graphs of maximum degree at most $d$ (isolated vertices are removed first), which is UG-hard; under $\mathrm{P}\neq\mathrm{NP}$ this contradicts UGC.
\end{proof}
Theorem~\ref{thm:ugc} and Corollary~\ref{cor:aks} are conditional implications, not claims about Algorithm~\ref{alg:main}. The theorem of~\cite{openai2026ugc} had not been peer reviewed at the time of writing; we cite it as reported and have not checked the formalization. Section~\ref{sec:ugcexp} reports the measured values of $|D|-i(h(H))$ and $|C_D|/\tau(H)$ on VC-IDS instances.
\section{A Reduction from Satisfiability}
\label{sec:sat}
A \emph{literal} is a variable $x$ or its negation $\neg x$, a \emph{clause} is a non-empty set of literals that does not contain a variable together with its negation, and a formula in conjunctive normal form is a list of clauses $C_1,\dots,C_q$; it is \emph{satisfiable} if some assignment of the variables makes true at least one literal of every clause. Deciding whether a formula is satisfiable is NP-complete~\cite{cook1971complexity}. A clause that contains a variable and its negation is satisfied by every assignment and can be deleted, and a formula with an empty clause is unsatisfiable, so these restrictions lose no generality. Let $\varphi$ be a formula, $x_1,\dots,x_N$ the variables that occur in it, $N\ge1$, $\Lambda=\sum_{i=1}^q|C_i|$ its number of literal occurrences and $W=\max_i|C_i|$ its largest clause width; a clause holds at most one literal of each variable, so $W\le N$.
\begin{Definition}[Graph of a formula with $t$ copies]
\label{def:satgraph}
For an integer $t\ge1$, the graph $G_{\varphi,t}$ has one \emph{literal vertex} $[\ell]$ for each of the $2N$ literals $\ell$ and $t$ \emph{clause vertices} $c_i^1,\dots,c_i^t$ for each clause $C_i$. Its edges are $\{[x_j],[\neg x_j]\}$ for $j=1,\dots,N$ and $\{c_i^r,[\ell]\}$ for every $i$, every $r$ and every literal $\ell\in C_i$. It has $2N+tq$ vertices and $N+t\Lambda$ edges.
\end{Definition}
For an assignment $\tau$, let $D_\tau$ be the set of the vertices $[\ell]$ of the literals $\ell$ that $\tau$ makes true.
\begin{Theorem}[Independent dominating sets of $G_{\varphi,t}$]
\label{thm:satgraph}
Let $t\ge W$. If $\tau$ satisfies $\varphi$, then $D_\tau$ is an independent dominating set of $G_{\varphi,t}$ with $N$ vertices. Every independent dominating set $D$ of $G_{\varphi,t}$ satisfies exactly one of the following: (i) $D$ contains no clause vertex, and then $D=D_\tau$ for an assignment $\tau$ that satisfies $\varphi$, so $|D|=N$; (ii) $D$ contains all the $t$ copies of $k\ge1$ clauses and no other clause vertex, and then $|D|=kt+N-\lambda$, where $\lambda$ is the number of variables $x_j$ with $[x_j]\notin D$ and $[\neg x_j]\notin D$, $2\lambda\le kW$, $\lambda=0$ if $k=1$, and $|D|\ge t+N$. Consequently $i(G_{\varphi,t})=N$ if $\varphi$ is satisfiable, and $i(G_{\varphi,t})\ge t+N$ otherwise.
\end{Theorem}
\begin{proof}
Let $\tau$ satisfy $\varphi$. $D_\tau$ holds exactly one of $[x_j]$ and $[\neg x_j]$ for every $j$ and no clause vertex, and the only edges between literal vertices are the edges $\{[x_j],[\neg x_j]\}$, so $D_\tau$ is independent. A literal vertex $[\ell]\notin D_\tau$ is adjacent to $[\neg\ell]\in D_\tau$, and a clause vertex $c_i^r$ is adjacent to $[\ell]\in D_\tau$ for a literal $\ell\in C_i$ that $\tau$ makes true. Hence $D_\tau$ is an independent dominating set, and $|D_\tau|=N$.
Let $D$ be an independent dominating set. (i) Suppose that $D$ contains no clause vertex. $D$ holds at most one of the adjacent vertices $[x_j]$, $[\neg x_j]$; the neighbours of $[x_j]$ are $[\neg x_j]$ and clause vertices, so $[x_j]\in D$ or $[\neg x_j]\in D$. Hence $D$ holds exactly one literal vertex of every variable, $D=D_\tau$ for the assignment $\tau$ that makes the literals of $D$ true, and $|D|=N$. A clause vertex $c_i^1$ is not in $D$, so it has a neighbour $[\ell]\in D$ with $\ell\in C_i$, and $\tau$ makes $\ell$ true: $\tau$ satisfies $\varphi$.
(ii) Suppose that $D$ contains a clause vertex, and let $H$ be the set of the indices $i$ such that $D$ contains a copy of $C_i$, with $k=|H|\ge1$. Let $i\in H$ and $c_i^r\in D$. By independence no vertex $[\ell]$ with $\ell\in C_i$ is in $D$. Every copy $c_i^s$ has exactly these neighbours, so it is not dominated by another vertex and $c_i^s\in D$. Hence $D$ contains the $t$ copies of each clause $C_i$ with $i\in H$ and no other clause vertex, that is, $kt$ clause vertices. $D$ holds at most one of $[x_j]$ and $[\neg x_j]$ for every $j$, and none of them exactly for the $\lambda$ variables counted in the statement, so $|D|=kt+N-\lambda$. Let $x_j$ be such a variable. The vertex $[x_j]$ is dominated, its neighbour $[\neg x_j]$ is not in $D$, and its other neighbours are copies of the clauses that contain $x_j$, so $x_j\in C_i$ for some $i\in H$; in the same way $\neg x_j\in C_{i'}$ for some $i'\in H$, and $i'\ne i$ because no clause contains both literals of a variable. So every such variable has one literal occurrence in each of two different clauses of $H$, and different variables give different occurrences. The clauses of $H$ have at most $kW$ literal occurrences, so $2\lambda\le kW$, and $\lambda=0$ if $k=1$. If $k=1$, then $|D|=t+N$. If $k\ge2$, then, by $t\ge W$,
\[
|D|\ge kt+N-\frac{kW}{2}=t+N+(k-1)t-\frac{kW}{2}\ge t+N+\Bigl(\frac k2-1\Bigr)W\ge t+N .
\]
The two cases exclude each other. If $\varphi$ is satisfiable, the sets of case (i) exist and have $NN(2N+q)^{1-\varepsilon}$ and $t>N^{1/\varepsilon}\ge N\ge W$. The graph $G=G_{\varphi,t}$ has $n=2N+tq\le t(2N+q)$ vertices, and for a fixed $\varepsilon$ its size is polynomial in $N+q+\Lambda$, since $t\le N^{1/\varepsilon}(2N+q)^{(1-\varepsilon)/\varepsilon}+1$. Let $S$ be the set that the algorithm returns on $G$. If $\varphi$ is satisfiable, $i(G)=N$ by Theorem~\ref{thm:satgraph}, and
\[
|S|\le n^{1-\varepsilon}N\le t^{1-\varepsilon}(2N+q)^{1-\varepsilon}N0$ directly from satisfiability: the graph of a satisfiable formula has an independent dominating set with $N$ vertices, every independent dominating set that is not a satisfying assignment has at least $t+N$ vertices, and no gap is obtained from the PCP theorem.
\section{Experiments}
\label{sec:experiments}
All experiments use \textsc{Siriaisa} 0.0.9 and the scripts of the folder \texttt{car/} of the repository: \texttt{run\_car.py} (Section~\ref{sec:suite}), \texttt{car\_bipartite.py} (Section~\ref{sec:bipartite}), \texttt{car\_ugc.py} (Section~\ref{sec:ugcexp}), and \texttt{car\_split.py}, \texttt{car\_cubic.py}, \texttt{car\_circle.py} and \texttt{car\_bounded.py} (Section~\ref{sec:splitexp}); Section~\ref{sec:dimacs} uses the command \texttt{batch\_iris} of the package. The scripts were written with Claude (Claude Opus 5.5) and run by the author; they import the repository's own \texttt{siriaisa/}, so they run whether or not the package is installed. The environment is Windows 11, Python 3.12.3, NetworkX 3.6.1~\cite{hagberg2008exploring}, NumPy 2.4.6 and SciPy 1.17.1~\cite{virtanen2020scipy}; wall-clock times are machine dependent.
\subsection{Reference values}
\label{sec:reference}
The reference values are computed by the scripts only and are never given to \textsc{Siriaisa}; every set returned by \textsc{Siriaisa} or by an integer program is verified to be an independent dominating set (respectively a vertex cover or a set cover) before its size is used.
\begin{itemize}
\item \emph{Integer programs.} The optimum $i(G)$ is the value of
\[
\min\sum_{v\in V}x_v\quad\text{s.t.}\quad\sum_{u\in N[v]}x_u\ge1\ \ \forall v\in V,\qquad x_u+x_v\le1\ \ \forall\{u,v\}\in E,\qquad x\in\{0,1\}^V,
\]
solved by \texttt{scipy.optimize.milp}, which calls the HiGHS branch-and-cut solver~\cite{huangfu2018parallelizing}, with a sparse constraint matrix (\texttt{scipy.sparse}) and a time limit. When HiGHS reports an optimal status, the rounded objective is $i(G)$. When the time limit is reached, the dual bound \texttt{mip\_dual\_bound} of HiGHS gives the certified lower bound $\lceil L\rceil\le i(G)$, and the incumbent, if any, an upper bound; the interval $[\lceil L\rceil,\min(|S|,\text{incumbent})]$ is reported and the instance is \emph{open} unless $|S|=\lceil L\rceil$. The vertex cover program ($\min\sum x_v$, $x_u+x_v\ge1$) and the set cover program ($\min\sum_Sx_S$, $\sum_{S\ni e}x_S\ge1$) are solved in the same way.
\item \emph{Linear relaxation of vertex cover.} For the VC-IDS instances, the value of the linear relaxation of vertex cover is half the size of a maximum matching of the bipartite double cover $H\times K_2$~\cite{nemhauser1975vertex}; it is computed with the Hopcroft--Karp algorithm~\cite{hopcroft1973n52} of NetworkX (\texttt{bipartite.hopcroft\_karp\_matching}) and rounded up, a certified lower bound on $\tau(H)$ that needs no time limit.
\item \emph{Closed forms and identities.} $i=\lceil n/3\rceil$ for paths and cycles, $i(K_{a,b})=\min(a,b)$ and $i=2$ for crown graphs, checked against the integer program whenever it proves optimality; on a complete multipartite graph, in which every maximal independent set is a whole part, $i$ is the size of the smallest part, and \texttt{car\_split.py} uses this value for its complete, complete bipartite and complete multipartite graphs without an integer program; $i=\mathrm{sc}+|\mathcal S|$ for SC-IDS~\cite{chlebik2008approximation} and $i(h(H))=\tau(H)+2m_H$ for VC-IDS (Proposition~\ref{prop:vcids}), which turn bounds on $\mathrm{sc}$ and $\tau$ into bounds on $i$.
\item \emph{Constructive upper bounds.} For the Khot--Regev instances, the planted cover of the reduction, made independent greedily on violated constraints, bounds $\tau(H)$ from above, and the construction of Proposition~\ref{prop:vcids} turns it into an explicit independent dominating set of $h(H)$, which is verified; the cover $C_D$ decoded from the output of \textsc{Siriaisa} (Lemma~\ref{lem:decode}) is a second upper bound.
\item \emph{Generators.} All random graphs are built with NetworkX generators (\texttt{gnp\_random\_graph}, \texttt{bipartite.random\_graph}, \texttt{random\_regular\_graph}, \texttt{bipartite.configuration\_model}, \texttt{random\_labeled\_tree} and others), each with its own seed derived from the master seed and the instance name.
\item \emph{Two runs of the references.} Every integer program, and every reference built from it, was computed in two runs of the scripts on the same instances (the same seeds and generators); the reference of an instance combines them, with the larger of the two certified lower bounds and the smaller of the two upper bounds. The sizes returned by \textsc{Siriaisa} are the same in both runs, and the times reported are those of the second run.
\end{itemize}
The certified lower bound $LB$ of Lemma~\ref{lem:lb} is used inside \textsc{Siriaisa} to stop its searches, not as a reference value.
\subsection{Structured and random families}
\label{sec:suite}
The script \texttt{run\_car.py} generates $10\,000$ instances with at most $40$ vertices from fifteen families (master seed $12345$) and computes the exact optimum by the integer program with a time limit of $30$\,s. Every instance is tagged with the bound of Corollary~\ref{cor:delta} for its family: $1$ for the rigid families, and the maximum degree for the bounded-degree and random families. Table~\ref{tab:suite} reports the results. The output is optimal on $9\,999$ instances; the remaining one is a Barab{\'a}si--Albert graph with $n=20$, $m=36$ and $\Delta=7$, on which $|S|=6$ and $i(G)=5$. No instance exceeds its bound. \textsc{Siriaisa} took $73.8$\,ms per instance on average, and the integer program $20.0$\,ms.
\begin{table}[H]
\centering
\small
\caption{The suite of $10\,000$ graphs: number of instances, optimal outputs, mean and maximum ratio $|S|/i(G)$, the largest bound of Corollary~\ref{cor:delta} in the family, the mean maximum degree and the number of instances above the bound.}
\label{tab:suite}
\begin{tabular}{llrrrrrrr}
\toprule
Family & Kind & Inst. & Opt. & Mean & Max & Bound & Mean $\Delta$ & Viol. \\
\midrule
clique & rigid & 667 & 667 & 1.0000 & 1.0000 & 1 & 6.47 & 0 \\
complete bipartite & rigid & 667 & 667 & 1.0000 & 1.0000 & 1 & 8.49 & 0 \\
crown & rigid & 666 & 666 & 1.0000 & 1.0000 & 1 & 3.09 & 0 \\
double star & rigid & 666 & 666 & 1.0000 & 1.0000 & 1 & 9.32 & 0 \\
star & rigid & 667 & 667 & 1.0000 & 1.0000 & 1 & 14.98 & 0 \\
balanced tree & bounded & 667 & 667 & 1.0000 & 1.0000 & 4 & 3.49 & 0 \\
cycle & bounded & 667 & 667 & 1.0000 & 1.0000 & 2 & 2.00 & 0 \\
grid & bounded & 667 & 667 & 1.0000 & 1.0000 & 4 & 3.60 & 0 \\
ladder & bounded & 667 & 667 & 1.0000 & 1.0000 & 3 & 2.95 & 0 \\
lollipop & bounded & 667 & 667 & 1.0000 & 1.0000 & 8 & 5.52 & 0 \\
path & bounded & 667 & 667 & 1.0000 & 1.0000 & 2 & 1.98 & 0 \\
random regular & bounded & 667 & 667 & 1.0000 & 1.0000 & 5 & 3.53 & 0 \\
Barab\'asi--Albert & random & 666 & 665 & 1.0003 & 1.2000 & 21 & 8.91 & 0 \\
Erd\H{o}s--R\'enyi & random & 666 & 666 & 1.0000 & 1.0000 & 20 & 8.07 & 0 \\
random tree & random & 666 & 666 & 1.0000 & 1.0000 & 7 & 3.77 & 0 \\
\midrule
\textbf{All} & & \textbf{10000} & \textbf{9999} & \textbf{1.0000} & \textbf{1.2000} & & & \textbf{0} \\
\bottomrule
\end{tabular}
\end{table}
\subsection{Baseline heuristics}
\label{sec:baselines}
The script \texttt{car\_baselines.py} runs four baseline heuristics on the $10\,000$ instances of Section~\ref{sec:suite}, with the optima of that section as references: a random maximal independent set of NetworkX (\texttt{maximal\_independent\_set}); the minimum-degree greedy, which selects a free vertex with the fewest free neighbours and deletes its closed neighbourhood; the maximum-degree greedy, which selects a free vertex with the most free neighbours; and the maximum-degree greedy followed by a local search with the $2$-swap move of~\cite{haraguchi2018efficient}, in which two vertices of the set are dropped and one vertex is added, applied until no such move exists. Every set is verified to be an independent dominating set. Table~\ref{tab:baselines} reports, for every family and every method, the number of optimal outputs and the mean and maximum ratio. Over the $10\,000$ instances, \textsc{Siriaisa} is optimal on $9\,999$, the random maximal independent set on $2\,301$, the minimum-degree greedy on $1\,253$, the maximum-degree greedy on $7\,262$, and the maximum-degree greedy with the $2$-swap search on $7\,920$; the largest ratios are $1.2$, $30$, $30$, $2$ and $2$. The mean time per instance in this run is $29.1$\,ms for \textsc{Siriaisa} and $0.032$\,ms, $0.034$\,ms, $0.022$\,ms and $0.035$\,ms for the four baselines.
\begin{table}[H]
\centering
\scriptsize
\caption{\textsc{Siriaisa} and four baseline heuristics on the suite of $10\,000$ graphs: number of optimal outputs (Opt.) and mean and maximum ratio to the optimum (file \texttt{car\_baselines\_summary.csv}).}
\label{tab:baselines}
\resizebox{\textwidth}{!}{%
\begin{tabular}{lrrrrrrrrrrrrrrrr}
\toprule
& & \multicolumn{3}{c}{\textsc{Siriaisa}} & \multicolumn{3}{c}{Random maximal} & \multicolumn{3}{c}{Min-degree greedy} & \multicolumn{3}{c}{Max-degree greedy} & \multicolumn{3}{c}{Max-degree + $2$-swap} \\
Family & Inst. & Opt. & Mean & Max & Opt. & Mean & Max & Opt. & Mean & Max & Opt. & Mean & Max & Opt. & Mean & Max \\
\midrule
balanced\_tree & 667 & 667 & 1.000 & 1.000 & 12 & 2.150 & 3.333 & 0 & 2.658 & 3.333 & 329 & 1.203 & 1.400 & 329 & 1.203 & 1.400 \\
barabasi\_albert & 666 & 665 & 1.000 & 1.200 & 44 & 1.684 & 6.000 & 3 & 1.921 & 6.000 & 452 & 1.089 & 2.000 & 474 & 1.079 & 2.000 \\
clique & 667 & 667 & 1.000 & 1.000 & 667 & 1.000 & 1.000 & 667 & 1.000 & 1.000 & 667 & 1.000 & 1.000 & 667 & 1.000 & 1.000 \\
complete\_bipartite & 667 & 667 & 1.000 & 1.000 & 250 & 2.352 & 12.000 & 57 & 2.646 & 12.000 & 667 & 1.000 & 1.000 & 667 & 1.000 & 1.000 \\
crown & 666 & 666 & 1.000 & 1.000 & 251 & 1.811 & 3.000 & 117 & 2.045 & 3.000 & 666 & 1.000 & 1.000 & 666 & 1.000 & 1.000 \\
cycle & 667 & 667 & 1.000 & 1.000 & 124 & 1.210 & 1.500 & 70 & 1.356 & 1.500 & 667 & 1.000 & 1.000 & 667 & 1.000 & 1.000 \\
double\_star & 666 & 666 & 1.000 & 1.000 & 100 & 2.305 & 6.500 & 5 & 2.599 & 6.500 & 666 & 1.000 & 1.000 & 666 & 1.000 & 1.000 \\
erdos\_renyi & 666 & 666 & 1.000 & 1.000 & 71 & 1.472 & 2.667 & 27 & 1.704 & 3.000 & 332 & 1.146 & 2.000 & 417 & 1.095 & 2.000 \\
grid & 667 & 667 & 1.000 & 1.000 & 123 & 1.361 & 2.000 & 24 & 1.629 & 2.000 & 111 & 1.309 & 1.667 & 248 & 1.197 & 1.667 \\
ladder & 667 & 667 & 1.000 & 1.000 & 72 & 1.439 & 1.857 & 33 & 1.673 & 1.889 & 75 & 1.268 & 1.500 & 260 & 1.117 & 1.333 \\
lollipop & 667 & 667 & 1.000 & 1.000 & 165 & 1.325 & 2.000 & 47 & 1.472 & 2.000 & 667 & 1.000 & 1.000 & 667 & 1.000 & 1.000 \\
path & 667 & 667 & 1.000 & 1.000 & 90 & 1.277 & 2.000 & 31 & 1.459 & 2.000 & 667 & 1.000 & 1.000 & 667 & 1.000 & 1.000 \\
random\_tree & 666 & 666 & 1.000 & 1.000 & 94 & 1.373 & 3.000 & 40 & 1.548 & 3.000 & 385 & 1.075 & 2.000 & 468 & 1.046 & 1.667 \\
regular & 667 & 667 & 1.000 & 1.000 & 147 & 1.274 & 2.500 & 99 & 1.417 & 2.500 & 244 & 1.161 & 1.750 & 390 & 1.081 & 1.667 \\
star & 667 & 667 & 1.000 & 1.000 & 91 & 14.063 & 30.000 & 33 & 14.979 & 30.000 & 667 & 1.000 & 1.000 & 667 & 1.000 & 1.000 \\
\midrule
All & 10000 & 9999 & 1.000 & 1.200 & 2301 & 2.407 & 30.000 & 1253 & 2.674 & 30.000 & 7262 & 1.083 & 2.000 & 7920 & 1.055 & 2.000 \\
\bottomrule
\end{tabular}%
}
\end{table}
\subsection{Bipartite graphs}
\label{sec:bipartite}
MIDS is NP-complete on bipartite graphs~\cite{loverov2020np}, so on these graphs there is no K\H{o}nig-type formula for the optimum. The script \texttt{car\_bipartite.py} (option \texttt{--quick}) generates $112$ bipartite graphs with $64$ to $256$ vertices from sixteen families: random bipartite graphs $G(n_1,n_2,p)$, balanced and with sides $1:2$, of average degree $3$, $6$ and $20$; random $d$-regular bipartite graphs ($d=3,4,8$); bipartite graphs with power-law degrees; double covers $G\times K_2$ of random $3$- and $5$-regular graphs; a perfect matching plus random edges; random trees, paths and even cycles; 2D and 3D grids, 2D grids with $30\%$ of the edges deleted; complete bipartite and crown graphs; hypercubes $Q_6$, $Q_8$ and their random halves. Labels are shuffled and every instance has its own generator, derived from the seed $20261031$ and its name. The reference is the integer program with a time limit of $60$\,s and the closed forms of Section~\ref{sec:reference}.
Table~\ref{tab:bipartite} reports the results. The optimum was proved on $95$ instances, and the output is optimal on all of them. On the $17$ open instances, all with $n\ge200$, the ratio column gives the certified upper bound $|S|/\lceil L\rceil$; on $8$ of them $|S|$ equals the best solution found by the integer programs, on $7$ it is smaller, and on two ($G(n/3,2n/3,p)$ with $n=200$ and average degree $20$) it exceeds it by one vertex ($15$ against $14$, and $16$ against $15$). The strategies $c_9$ and $c_{11}$ were exact (one forest layer, empty core) on the $8$ trees and paths, as Theorem~\ref{thm:forest} requires. \textsc{Siriaisa} took at most $12.1$\,s per instance and $391.0$\,s in total; the integer programs took $1\,453.9$\,s and the whole run $1\,847.2$\,s.
\begin{table}[H]
\centering
\scriptsize
\caption{Bipartite graphs: instances, instances with the optimum proved (``Ref.''), optimal, suboptimal and open outputs, maximum and mean ratio (certified upper bounds on open instances), and the time of \textsc{Siriaisa} in seconds.}
\label{tab:bipartite}
\resizebox{\textwidth}{!}{%
\begin{tabular}{lrrrrrrrr}
\toprule
Family & Inst. & Ref. & Opt. & Subopt. & Open & Max ratio & Mean ratio & Time \\
\midrule
2D grid & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 4.8 \\
2D grid, 70\% edges kept & 6 & 6 & 6 & 0 & 0 & 1.0000 & 1.0000 & 30.0 \\
3D grid & 2 & 1 & 1 & 0 & 1 & 1.0750 & 1.0375 & 5.6 \\
complete bipartite & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 3.4 \\
crown graph & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 0.2 \\
double cover $G\times K_2$ of random regular & 12 & 8 & 8 & 0 & 4 & 1.1765 & 1.0370 & 46.9 \\
even cycle & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 0.0 \\
hidden perfect matching + random edges & 12 & 12 & 12 & 0 & 0 & 1.0000 & 1.0000 & 42.3 \\
hypercube & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 4.9 \\
hypercube, 50\% edges kept & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 10.9 \\
path & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 0.0 \\
power-law bipartite & 6 & 6 & 6 & 0 & 0 & 1.0000 & 1.0000 & 25.1 \\
random bipartite (1:2) & 18 & 15 & 15 & 0 & 3 & 1.4545 & 1.0657 & 56.9 \\
random bipartite (balanced) & 18 & 15 & 15 & 0 & 3 & 1.4167 & 1.0602 & 60.7 \\
random $d$-regular bipartite & 18 & 12 & 12 & 0 & 6 & 1.2917 & 1.0623 & 78.9 \\
random tree & 6 & 6 & 6 & 0 & 0 & 1.0000 & 1.0000 & 20.3 \\
\midrule
\textbf{All} & \textbf{112} & \textbf{95} & \textbf{95} & \textbf{0} & \textbf{17} & \textbf{1.4545} & \textbf{1.0349} & \textbf{391.0} \\
\bottomrule
\end{tabular}%
}
\end{table}
\subsection{Instances of the hardness reductions}
\label{sec:ugcexp}
The script \texttt{car\_ugc.py} (option \texttt{--quick}, integer programs limited to $60$\,s) builds $55$ instances of the two reductions of Section~\ref{sec:hardness}. The SC-IDS instances are bipartite, of maximum degree $B\in\{4,5,6\}$, built from random set systems with $30$ or $60$ sets of size $B-1$ in which every element lies in at most $B$ sets; the reference is the set cover integer program and $i=\mathrm{sc}+|\mathcal S|$. The VC-IDS instances are $h(H)$, none of whose graphs $H$ has an isolated vertex, for random $d$-regular graphs $H$ with $d\in\{3,4,5\}$ and $50$, $100$ or $200$ vertices, of maximum degree $d$, and for ten Khot--Regev YES instances $H$ with $640$ vertices (seed $20261009$, the instances and names of Part~D of the \textsc{Salvador} experiments~\cite{Vega26SalvadorPaper}: a Unique Games instance on a random $4$-regular graph with $40$ vertices and a planted labelling, $16$ subsets per block drawn from the $p$-biased measure, the base family $k=4$, $p=0.45$, $\eta=0$ and the variants $k=3$, $p=0.35$, $\eta=0.1$ and linear constraints, two instances each~\cite{khot2008vertex}); these $h(H)$ have $48\,172$ to $75\,166$ vertices and maximum degree $64$. The reference is $\tau(H)$: $L_\tau$ is the larger of the linear relaxation and the integer-program dual bound, and $U_\tau$ the smaller of the integer-program value, the planted cover and the decoded cover of Lemma~\ref{lem:decode}; by Proposition~\ref{prop:vcids}, $L_\tau+2m_H\le i(h(H))\le U_\tau+2m_H$, with equality when $L_\tau=U_\tau$ (Section~\ref{sec:reference}).
Table~\ref{tab:ugc} reports the results. On the $18$ SC-IDS instances the output is optimal. On the VC-IDS instances $\tau(H)$ was proved on $30$ of $37$; on these the output is optimal on $2$ (one $3$-regular and one $4$-regular graph with $50$ vertices) and exceeds the optimum on $28$; the certified ratio $|D|/L$ is at most $1.0175$ on the instances of Khot and Regev and at most $1.0375$ on the regular graphs, and the largest excess $|D|-L$ is $292$ vertices. The decoded cover satisfies $|C_D|/L_\tau\le1.35$ on the regular graphs and lies between $1.25$ and $1.8665$ on the instances of Khot and Regev (mean $1.4826$), where the planted cover has $347$ to $416$ vertices and the decoded cover $480$ to $629$. The random regular graphs $H$ are not the hard instances of~\cite{austrin2011inapproximability}, so they measure the algorithm on bounded-degree VC-IDS graphs without testing Corollary~\ref{cor:aks}. The whole run took $1\,654.0$\,s; \textsc{Siriaisa} took at most $72.8$\,s per instance.
\begin{table}[H]
\centering
\scriptsize
\caption{Instances of the reductions of Chleb{\'\i}k and Chleb{\'\i}kov{\'a}. ``Ref.'' counts instances with $i$ proved; ``Opt.'', ``Subopt.'' and ``Open'' classify $|D|$ against it; ``max $|D|/L$'' is the largest certified ratio, ``max exc.'' the largest $|D|-L$; the last two columns give the number of optimal decoded covers and the largest $|C_D|/L_\tau$.}
\label{tab:ugc}
\resizebox{\textwidth}{!}{%
\begin{tabular}{lrrrrrrrrrr}
\toprule
Family & Inst. & $n$ & $\Delta$ & Ref. & Opt. & Subopt. & Open & max $|D|/L$ & max exc. & $C_D$ opt. / max $|C_D|/L_\tau$ \\
\midrule
SC-IDS, $B=4$ & 6 & 113--225 & 4 & 6 & 6 & 0 & 0 & 1.0000 & 0 & --- \\
SC-IDS, $B=5$ & 6 & 108--228 & 5 & 6 & 6 & 0 & 0 & 1.0000 & 0 & --- \\
SC-IDS, $B=6$ & 6 & 106--224 & 6 & 6 & 6 & 0 & 0 & 1.0000 & 0 & --- \\
VC-IDS, $3$-regular $H$ & 9 & 500--2\,000 & 3 & 9 & 1 & 8 & 0 & 1.0309 & 22 & 1 / 1.1982 \\
VC-IDS, $4$-regular $H$ & 9 & 650--2\,600 & 4 & 8 & 1 & 7 & 1 & 1.0360 & 33 & 1 / 1.2821 \\
VC-IDS, $5$-regular $H$ & 9 & 800--3\,200 & 5 & 6 & 0 & 6 & 3 & 1.0375 & 42 & 0 / 1.3500 \\
VC-IDS, Khot--Regev $H$ & 10 & 48\,172--75\,166 & 64 & 7 & 0 & 7 & 3 & 1.0175 & 292 & 0 / 1.8665 \\
\midrule
\textbf{All} & \textbf{55} & & & \textbf{48} & \textbf{20} & \textbf{28} & \textbf{7} & \textbf{1.0375} & \textbf{292} & \textbf{2 / 1.8665} \\
\bottomrule
\end{tabular}%
}
\end{table}
\subsection{The splitting excess on hard families}
\label{sec:splitexp}
Four scripts measure the splitting excess $s(G)$ and the output on the families of Section~\ref{sec:ratio}; all of them were run with the option \texttt{--quick}, so that $n\le400$ on the random families, and the integer program has a time limit of $30$\,s for $n\le400$ (\texttt{car\_split.py}, \texttt{car\_cubic.py}, \texttt{car\_circle.py}) or of $60$\,s for $n\le1\,100$ (\texttt{car\_bounded.py}). Each script asserts on every instance the statements of Section~\ref{sec:ratio} that apply to it, and no assertion failed.
\paragraph{Hard and structured families} The script \texttt{car\_split.py} (seed $20261101$) builds $110$ instances of $29$ families and computes, on each, $k$, $B$, $s(G)$, the copy graph $H$ of Algorithm~\ref{alg:split}, the decoded set $S_0$ of each inner solver and whether it is independent in $G$; it asserts the bounds of Proposition~\ref{prop:sworst}(ii)--(iii), that $|V(H)|=n-|B|+\sum_{v\in B}\lceil\deg(v)/k\rceil$ and $\Delta(H)\le k$, that every $S_0$ dominates $G$ (Lemma~\ref{lem:decode-split}), and that $|S_0|\le k\,(U+s(G))$ (Theorem~\ref{thm:split}). Table~\ref{tab:split} reports the results. $s(G)=0$ on all $54$ instances of maximum degree at most $k$; the largest excess, $7\,600=s(K_{400})$, is attained by the complete graph, and $s(G)/n^{3/2}\le0.950$ on all instances. The decoded set $S_0$ of some inner solver is independent on $69$ instances, $15$ of them with $s(G)>0$, and the largest value of $|S_0|/(k\,(U+s(G)))$ is $0.1264$. The optimum is proved on $87$ instances, among them the $20$ complete, complete bipartite and complete multipartite graphs, for which $i$ is the size of the smallest part (Section~\ref{sec:reference}); the output is optimal on $79$ of them and exceeds the optimum by $1$ to $5$ vertices on the other $8$ (a Delaunay graph, an SC-IDS graph, $G(n,3/n)$, two Barab{\'a}si--Albert graphs and three Khot--Regev graphs of constraint degree $3$). On the $23$ open instances the lower bound is the integer-program dual bound for $n\le400$ and $\lceil n/(\Delta+1)\rceil$ otherwise; the ratios $15.9$ and $22.2$ of the Khot--Regev and VC-IDS Khot--Regev graphs are ratios to $\lceil n/(\Delta+1)\rceil$. The run took $1\,542.9$\,s.
\begin{table}[H]
\centering
\scriptsize
\caption{Splitting excess on hard and structured families ($k=\lfloor\sqrt n\rfloor$): largest maximum degree, instances with $s(G)=0$, largest $s(G)$ and $s(G)/n^{3/2}$, and instances on which the decoded set $S_0$ of some inner solver is independent. ``Ref.'' counts instances with $i(G)$ proved (integer program, closed form, planted value or reduction identity); ``Opt.'', ``Subopt.'' and ``Open'' classify the output against it; ``Max ratio'' is the largest $|S|/L$ for the certified lower bound $L$ (an upper bound on the ratio of open instances); ``Time'' is the total time of \textsc{Siriaisa} in seconds. $^{*}$Union of $d$ random perfect matchings with repeated edges merged (maximum degree $d$).}
\label{tab:split}
\resizebox{\textwidth}{!}{%
\begin{tabular}{lrrrrrrrrrrrrr}
\toprule
Family & Inst. & $n$ & $\Delta$ & $s=0$ & max $s$ & max $s/n^{3/2}$ & $S_0$ ind. & Ref. & Opt. & Subopt. & Open & Max ratio & Time \\
\midrule
random 3-regular bipartite$^{*}$ & 4 & 100--400 & 3 & 4 & 0 & 0.000 & 4 & 2 & 2 & 0 & 2 & 1.0784 & 38.0 \\
planar (Delaunay) & 4 & 100--400 & 12 & 4 & 0 & 0.000 & 4 & 4 & 3 & 1 & 0 & 1.0161 & 33.3 \\
random 4-regular & 4 & 100--400 & 4 & 4 & 0 & 0.000 & 4 & 2 & 2 & 0 & 2 & 1.1481 & 35.5 \\
random 5-regular & 4 & 100--400 & 5 & 4 & 0 & 0.000 & 4 & 2 & 2 & 0 & 2 & 1.2239 & 34.5 \\
random 6-regular & 4 & 100--400 & 6 & 4 & 0 & 0.000 & 4 & 2 & 2 & 0 & 2 & 1.2586 & 36.3 \\
random 4-regular bipartite$^{*}$ & 4 & 100--400 & 4 & 4 & 0 & 0.000 & 4 & 2 & 2 & 0 & 2 & 1.1481 & 32.3 \\
random 5-regular bipartite$^{*}$ & 4 & 100--400 & 5 & 4 & 0 & 0.000 & 4 & 2 & 2 & 0 & 2 & 1.2059 & 30.0 \\
SC-IDS, $B=4$ & 4 & 94--375 & 4 & 4 & 0 & 0.000 & 4 & 4 & 3 & 1 & 0 & 1.0080 & 33.0 \\
SC-IDS, $B=6$ & 4 & 93--384 & 6 & 4 & 0 & 0.000 & 4 & 4 & 4 & 0 & 0 & 1.0000 & 25.0 \\
VC-IDS, $3$-regular $H$ & 4 & 240--1\,000 & 3 & 4 & 0 & 0.000 & 4 & 2 & 2 & 0 & 2 & 1.4400 & 59.2 \\
$G(n,1/2)$ & 4 & 100--400 & 230 & 0 & 3\,783 & 0.473 & 0 & 2 & 2 & 0 & 2 & 2.5000 & 19.5 \\
complete $K_n$ & 4 & 100--400 & 399 & 0 & 7\,600 & 0.950 & 0 & 4 & 4 & 0 & 0 & 1.0000 & 4.9 \\
$K_{n/2,n/2}$ & 4 & 100--400 & 200 & 0 & 3\,600 & 0.450 & 4 & 4 & 4 & 0 & 0 & 1.0000 & 19.0 \\
$K_{n/4,3n/4}$ & 4 & 100--400 & 300 & 0 & 2\,600 & 0.325 & 2 & 4 & 4 & 0 & 0 & 1.0000 & 13.8 \\
complete $4$-partite, equal parts & 4 & 100--400 & 300 & 0 & 5\,600 & 0.700 & 0 & 4 & 4 & 0 & 0 & 1.0000 & 22.0 \\
complete $5$-partite, random parts & 4 & 100--400 & 392 & 0 & 5\,889 & 0.736 & 0 & 4 & 4 & 0 & 0 & 1.0000 & 17.8 \\
crown & 4 & 100--400 & 199 & 0 & 3\,600 & 0.450 & 0 & 4 & 4 & 0 & 0 & 1.0000 & 2.8 \\
star & 4 & 100--400 & 399 & 0 & 19 & 0.009 & 4 & 4 & 4 & 0 & 0 & 1.0000 & 0.1 \\
wheel & 4 & 100--400 & 399 & 0 & 19 & 0.009 & 4 & 4 & 4 & 0 & 0 & 1.0000 & 0.2 \\
double star & 4 & 100--400 & 200 & 0 & 18 & 0.008 & 0 & 4 & 4 & 0 & 0 & 1.0000 & 25.3 \\
split graph & 4 & 100--400 & 232 & 0 & 209 & 0.055 & 0 & 4 & 4 & 0 & 0 & 1.0000 & 7.7 \\
$G(n,3/n)$ & 4 & 100--400 & 11 & 4 & 0 & 0.000 & 4 & 4 & 3 & 1 & 0 & 1.0075 & 47.6 \\
Barab\'asi--Albert, $m=3$ & 4 & 100--400 & 67 & 0 & 19 & 0.013 & 0 & 4 & 2 & 2 & 0 & 1.0532 & 25.8 \\
power-law bipartite & 4 & 100--400 & 55 & 0 & 6 & 0.004 & 1 & 4 & 4 & 0 & 0 & 1.0000 & 43.9 \\
2D grid & 4 & 100--400 & 4 & 4 & 0 & 0.000 & 4 & 2 & 2 & 0 & 2 & 1.0814 & 31.2 \\
hypercube & 2 & 128--512 & 9 & 2 & 0 & 0.000 & 2 & 1 & 1 & 0 & 1 & 1.2308 & 4.8 \\
Khot--Regev YES & 2 & 640 & 64 & 0 & 323 & 0.020 & 0 & 0 & 0 & 0 & 2 & 15.9000 & 10.2 \\
Khot--Regev YES, $d=3$, $s_b\in\{4,8\}$ & 4 & 160--320 & 24 & 2 & 39 & 0.007 & 2 & 4 & 1 & 3 & 0 & 1.0361 & 23.7 \\
VC-IDS, Khot--Regev $H$ & 2 & 49\,096--51\,550 & 64 & 2 & 0 & 0.000 & 2 & 0 & 0 & 0 & 2 & 22.1825 & 87.0 \\
\midrule
\textbf{All} & \textbf{110} & & & \textbf{54} & \textbf{7\,600} & \textbf{0.950} & \textbf{69} & \textbf{87} & \textbf{79} & \textbf{8} & \textbf{23} & \textbf{22.1825} & \textbf{764.3} \\
\bottomrule
\end{tabular}%
}
\end{table}
\paragraph{Cubic graphs} The script \texttt{car\_cubic.py} (seed $20261102$) builds $61$ instances: every cubic graph on $4$, $6$ and $8$ vertices (one, two and six graphs, collected as isomorphism classes of random $3$-regular graphs), six random graphs of maximum degree $3$ on $3$ to $8$ vertices, twelve named cubic graphs, and random cubic, cubic bipartite (three edge-disjoint random perfect matchings), double covers of random cubic graphs, cubic planar (duals of Delaunay triangulations with a triangular outer face), cubic planar bipartite (grown from the cube by inserting two rungs across an even face, which preserves planarity, bipartiteness and degree $3$), random cubic graphs with $20\%$ of the edges deleted, prisms, M{\"o}bius ladders and generalized Petersen graphs with $100$ to $402$ vertices. It asserts Proposition~\ref{prop:cubic}(i)--(ii), that the copy graph equals $G$ when $s(G)=0$, and Theorem~\ref{thm:regular}: $|S|\le n/2$ on regular graphs and $|S|\le2L$ on cubic graphs. Table~\ref{tab:cubic} reports the results. On the cubic graphs, $s(G)=n$ for $n\in\{4,6,8\}$ and $s(G)=0$ for $n\ge10$, and on the graphs of maximum degree $3$ with $n\le8$, $s(G)\le6$. The optimum is proved on $49$ instances and the output is optimal on all of them; on the $12$ open instances, all with $400$ or $402$ vertices, $|S|/L\le1.0792$ except on $GP(200,2)$, where $|S|=120$ and $L=103$. $|S|/n$ is at most $0.5$, attained by $K_{3,3}$, and at most $0.3333$ for $n\ge10$; strategy $c_{13}$ alone is optimal on $15$ of the $30$ cubic graphs with $n\ge10$ and a proved optimum. The run took $564.1$\,s.
\begin{table}[H]
\centering
\scriptsize
\caption{Cubic and subcubic graphs: the values of $s(G)$, instances on which the copy graph is $G$ (no vertex split), the classification of the output, and the largest $|S|/n$. ``Ref.'' counts instances with $i(G)$ proved (integer program, closed form, planted value or reduction identity); ``Opt.'', ``Subopt.'' and ``Open'' classify the output against it; ``Max ratio'' is the largest $|S|/L$ for the certified lower bound $L$ (an upper bound on the ratio of open instances); ``Time'' is the total time of \textsc{Siriaisa} in seconds. $^{\dagger}$Petersen, Heawood, M\"obius--Kantor, Pappus, Desargues, dodecahedron, truncated tetrahedron, truncated cube, Frucht, Tutte, McGee and Foster graphs.}
\label{tab:cubic}
\resizebox{\textwidth}{!}{%
\begin{tabular}{lrrrrrrrrrrr}
\toprule
Family & Inst. & $n$ & $s(G)$ & $H=G$ & Ref. & Opt. & Subopt. & Open & Max ratio & max $|S|/n$ & Time \\
\midrule
cubic, $n=4$ & 1 & 4 & 4 & 0 & 1 & 1 & 0 & 0 & 1.0000 & 0.2500 & 0.0 \\
cubic, $n=6$ & 2 & 6 & 6 & 0 & 2 & 2 & 0 & 0 & 1.0000 & 0.5000 & 0.0 \\
cubic, $n=8$ & 6 & 8 & 8 & 0 & 6 & 6 & 0 & 0 & 1.0000 & 0.3750 & 0.0 \\
$\Delta\le3$, $n\le8$ & 6 & 3--8 & 1,4,5,6 & 0 & 6 & 6 & 0 & 0 & 1.0000 & 0.4000 & 0.0 \\
named cubic graphs$^{\dagger}$ & 12 & 10--90 & 0 & 12 & 12 & 12 & 0 & 0 & 1.0000 & 0.3333 & 2.1 \\
random cubic & 4 & 100--400 & 0 & 4 & 2 & 2 & 0 & 2 & 1.0693 & 0.2700 & 19.6 \\
random cubic bipartite & 4 & 100--400 & 0 & 4 & 2 & 2 & 0 & 2 & 1.0693 & 0.2700 & 25.1 \\
double cover of random cubic & 4 & 100--400 & 0 & 4 & 2 & 2 & 0 & 2 & 1.0693 & 0.2800 & 24.5 \\
cubic planar (dual of Delaunay) & 4 & 100--400 & 0 & 4 & 2 & 2 & 0 & 2 & 1.0792 & 0.2725 & 25.0 \\
cubic planar bipartite & 4 & 100--400 & 0 & 4 & 2 & 2 & 0 & 2 & 1.0588 & 0.2800 & 20.8 \\
random cubic, $20\%$ edges deleted & 4 & 100--400 & 0 & 4 & 4 & 4 & 0 & 0 & 1.0000 & 0.3250 & 25.1 \\
prism $C_t\times K_2$ & 4 & 100--402 & 0 & 4 & 3 & 3 & 0 & 1 & 1.0099 & 0.2600 & 13.2 \\
M\"obius ladder & 2 & 100--400 & 0 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 0.2525 & 10.3 \\
generalized Petersen $GP(t,2)$ & 2 & 100--400 & 0 & 2 & 1 & 1 & 0 & 1 & 1.1650 & 0.3000 & 11.7 \\
generalized Petersen $GP(t,3)$ & 2 & 100--400 & 0 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 0.2600 & 5.2 \\
\midrule
\textbf{All} & \textbf{61} & & & \textbf{46} & \textbf{49} & \textbf{49} & \textbf{0} & \textbf{12} & \textbf{1.1650} & \textbf{0.5000} & \textbf{182.7} \\
\bottomrule
\end{tabular}%
}
\end{table}
\paragraph{Circle graphs} The script \texttt{car\_circle.py} (seed $20261103$) builds $40$ circle graphs from chord models with $100$ and $400$ chords: chords with uniform random endpoints, short random chords of expected degree about $3$, $10$ and $\sqrt n$, permutation graphs, two or four long chords each crossed by nested short chords, and the models of Proposition~\ref{prop:circle}(ii) of $K_n$, $K_{n/2,n/2}$ and $K_{n/4,3n/4}$, a star, a path and a cycle. It computes the degrees and $s(G)$ from the model by Proposition~\ref{prop:circle}(i), checks them against the circle graph built from the crossings, and checks that the models of the complete, complete bipartite, star, path and cycle families give these graphs. Table~\ref{tab:circle} reports the results. The degrees from the model agree with the graph on all instances; computing $s(G)$ from the model took at most $1.4$\,ms per instance and building the graph at most $49$\,ms. The excess reaches $s(K_{400})=7\,600$ on the diameters, $s(G)/s(K_n)\le0.563$ on the other families, and $s(G)=0$ only on paths, cycles and three of the four sparsest random models. The optimum is proved on $38$ instances, with the closed forms $i(K_{a,b})=\min(a,b)$ and $i=\lceil n/3\rceil$ for paths and cycles; the output is optimal on $34$ and exceeds the optimum by $1$ to $3$ vertices on four graphs of short chords with $400$ chords; the two open instances are uniform random models with $400$ chords, with $|S|/L\le1.1905$. The run took $283.8$\,s.
\begin{table}[H]
\centering
\scriptsize
\caption{Circle graphs built from chord models: largest number of edges and maximum degree, instances with $s(G)=0$, largest $s(G)$ and $s(G)/s(K_n)$, instances with an independent decoded set $S_0$. ``Ref.'' counts instances with $i(G)$ proved (integer program, closed form, planted value or reduction identity); ``Opt.'', ``Subopt.'' and ``Open'' classify the output against it; ``Max ratio'' is the largest $|S|/L$ for the certified lower bound $L$ (an upper bound on the ratio of open instances); ``Time'' is the total time of \textsc{Siriaisa} in seconds.}
\label{tab:circle}
\resizebox{\textwidth}{!}{%
\begin{tabular}{lrrrrrrrrrrrrrr}
\toprule
Family & Inst. & $n$ & max $m$ & $\Delta$ & $s=0$ & max $s$ & max $s/s(K_n)$ & $S_0$ ind. & Ref. & Opt. & Subopt. & Open & Max ratio & Time \\
\midrule
uniform random chords & 4 & 100--400 & 27\,268 & 219 & 0 & 2\,513 & 0.331 & 0 & 2 & 2 & 0 & 2 & 1.1905 & 6.5 \\
short chords, degree $\approx3$ & 4 & 100--400 & 904 & 14 & 3 & 2 & 0.002 & 3 & 4 & 4 & 0 & 0 & 1.0000 & 19.4 \\
short chords, degree $\approx10$ & 4 & 100--400 & 2\,500 & 29 & 0 & 107 & 0.119 & 0 & 4 & 2 & 2 & 0 & 1.0405 & 12.5 \\
short chords, degree $\approx\sqrt n$ & 4 & 100--400 & 5\,488 & 57 & 0 & 354 & 0.092 & 0 & 4 & 2 & 2 & 0 & 1.0600 & 8.6 \\
permutation graph & 4 & 100--400 & 41\,274 & 393 & 0 & 3\,925 & 0.563 & 0 & 4 & 4 & 0 & 0 & 1.0000 & 11.0 \\
$2$ hub chords & 4 & 100--400 & 532 & 102 & 0 & 15 & 0.007 & 1 & 4 & 4 & 0 & 0 & 1.0000 & 16.5 \\
$4$ hub chords & 4 & 100--400 & 599 & 54 & 0 & 14 & 0.006 & 1 & 4 & 4 & 0 & 0 & 1.0000 & 16.9 \\
diameters ($K_n$) & 2 & 100--400 & 79\,800 & 399 & 0 & 7\,600 & 1.000 & 0 & 2 & 2 & 0 & 0 & 1.0000 & 0.8 \\
$K_{n/2,n/2}$ & 2 & 100--400 & 40\,000 & 200 & 0 & 3\,600 & 0.474 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 4.4 \\
$K_{n/4,3n/4}$ & 2 & 100--400 & 30\,000 & 300 & 0 & 2\,600 & 0.361 & 1 & 2 & 2 & 0 & 0 & 1.0000 & 5.0 \\
star $K_{1,n-1}$ & 2 & 100--400 & 399 & 399 & 0 & 19 & 0.010 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 0.0 \\
path & 2 & 100--400 & 399 & 2 & 2 & 0 & 0.000 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 0.0 \\
cycle & 2 & 100--400 & 400 & 2 & 2 & 0 & 0.000 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 0.1 \\
\midrule
\textbf{All} & \textbf{40} & & & & \textbf{7} & \textbf{7\,600} & \textbf{1.000} & \textbf{14} & \textbf{38} & \textbf{34} & \textbf{4} & \textbf{2} & \textbf{1.1905} & \textbf{101.7} \\
\bottomrule
\end{tabular}%
}
\end{table}
\paragraph{Bounded degree with $n\ge B^2$} On graphs of maximum degree at most $B$ with $n\ge B^2$, $s(G)=0$ (Proposition~\ref{prop:families}(a)), and MIDS is NP-hard to approximate within $\delta B$ for every $B\ge B_0$~\cite{chlebik2008approximation}. The script \texttt{car\_bounded.py} (seed $20261104$) builds $44$ such graphs for $B\in\{4,8,16,32\}$ with $n\ge\max(B^2,256)$: random $B$-regular graphs, double covers of random $B$-regular graphs, $B$-regular graphs with a planted perfect code, SC-IDS graphs of degree $B$ and VC-IDS graphs $h(H)$ of random $B$-regular graphs $H$, and Khot--Regev YES graphs with constraint degree $3$ and $s_b\in\{4,8\}$ samples per block ($\Delta\le3s_b$, with $9s_b+4$ blocks). A planted perfect code is a set $D$ of $t$ vertices, each with $B$ private neighbours, the $tB$ other vertices being joined by a random $(B-1)$-regular graph; the graph is $B$-regular, $D$ is an independent dominating set, and $|D|=n/(B+1)=\lceil n/(\Delta+1)\rceil$, so $i(G)=|D|$ by Lemma~\ref{lem:lb}. For SC-IDS and VC-IDS the identities $i=\mathrm{sc}+|\mathcal S|$ and $i=\tau(H)+2m_H$, with $\mathrm{sc}$ and $\tau(H)$ bounded by integer programs, narrow the interval. The script asserts $s(G)=0$, $|S|\le n/2$ on the regular graphs and that the planted code has size $\lceil n/(\Delta+1)\rceil$. Table~\ref{tab:bounded} reports the results. $s(G)=0$ on all $44$ instances. The optimum is proved on $26$ instances and the output is optimal on $18$ of them, among them all $8$ planted perfect codes, on graphs with up to $1\,056$ vertices and $16\,896$ edges; it exceeds the optimum by $1$ vertex on two SC-IDS graphs and three VC-IDS graphs of degree $16$ and $32$, and by $2$, $1$ and $4$ vertices on three Khot--Regev graphs. On the $16$ open random regular graphs the integer program did not improve on $\lceil n/(\Delta+1)\rceil$, and $|S|/L$ grows from $1.1346$ for $B=4$ to $2.2500$ for $B=32$; on the two open SC-IDS graphs of degree $32$ the output has $357$ and $355$ vertices against the integer-program bound $348$ and $L=338$. The largest time of \textsc{Siriaisa} on an instance is $12.7$\,s, and the run took $1\,579.5$\,s.
\begin{table}[H]
\centering
\scriptsize
\caption{Graphs of maximum degree $B$ with $n\ge B^2$, on which $s(G)=0$: instances, number of vertices and largest number of edges, instances with $s(G)=0$, the classification of the output, and the largest and mean $|S|/L$. ``Ref.'' counts instances with $i(G)$ proved (integer program, closed form, planted value or reduction identity); ``Opt.'', ``Subopt.'' and ``Open'' classify the output against it; ``Max ratio'' is the largest $|S|/L$ for the certified lower bound $L$ (an upper bound on the ratio of open instances); ``Time'' is the total time of \textsc{Siriaisa} in seconds.}
\label{tab:bounded}
\resizebox{\textwidth}{!}{%
\begin{tabular}{lrrrrrrrrrrrr}
\toprule
Family & $B$ & Inst. & $n$ & max $m$ & $s=0$ & Ref. & Opt. & Subopt. & Open & Max ratio & Mean ratio & Time \\
\midrule
random $B$-regular & 4 & 2 & 256 & 512 & 2 & 0 & 0 & 0 & 2 & 1.1346 & 1.1346 & 10.9 \\
random $B$-regular bipartite (double cover) & 4 & 2 & 256 & 512 & 2 & 0 & 0 & 0 & 2 & 1.1154 & 1.1058 & 10.9 \\
$B$-regular, planted perfect code & 4 & 2 & 260 & 520 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 1.1 \\
SC-IDS & 4 & 2 & 323 & 430 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 18.4 \\
VC-IDS, $B$-regular $H$ & 4 & 2 & 260 & 320 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 20.0 \\
random $B$-regular & 8 & 2 & 256 & 1\,024 & 2 & 0 & 0 & 0 & 2 & 1.3793 & 1.3621 & 8.5 \\
random $B$-regular bipartite (double cover) & 8 & 2 & 256 & 1\,024 & 2 & 0 & 0 & 0 & 2 & 1.3448 & 1.3448 & 6.7 \\
$B$-regular, planted perfect code & 8 & 2 & 261 & 1\,044 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 0.6 \\
SC-IDS & 8 & 2 & 331--334 & 769 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 13.5 \\
VC-IDS, $B$-regular $H$ & 8 & 2 & 250 & 320 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 24.8 \\
random $B$-regular & 16 & 2 & 256 & 2\,048 & 2 & 0 & 0 & 0 & 2 & 1.5625 & 1.5312 & 4.0 \\
random $B$-regular bipartite (double cover) & 16 & 2 & 256 & 2\,048 & 2 & 0 & 0 & 0 & 2 & 1.5625 & 1.5625 & 5.0 \\
$B$-regular, planted perfect code & 16 & 2 & 272 & 2\,176 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 0.7 \\
SC-IDS & 16 & 2 & 318--321 & 1\,353 & 2 & 2 & 0 & 2 & 0 & 1.0115 & 1.0114 & 11.4 \\
VC-IDS, $B$-regular $H$ & 16 & 2 & 882 & 1\,152 & 2 & 2 & 1 & 1 & 0 & 1.0033 & 1.0016 & 19.8 \\
random $B$-regular & 32 & 2 & 1\,024 & 16\,384 & 2 & 0 & 0 & 0 & 2 & 2.2188 & 2.2188 & 5.8 \\
random $B$-regular bipartite (double cover) & 32 & 2 & 1\,024 & 16\,384 & 2 & 0 & 0 & 0 & 2 & 2.2500 & 2.2500 & 4.2 \\
$B$-regular, planted perfect code & 32 & 2 & 1\,056 & 16\,896 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 1.5 \\
SC-IDS & 32 & 2 & 1\,313 & 10\,787 & 2 & 0 & 0 & 0 & 2 & 1.0562 & 1.0533 & 7.1 \\
VC-IDS, $B$-regular $H$ & 32 & 2 & 3\,298 & 4\,352 & 2 & 2 & 0 & 2 & 0 & 1.0009 & 1.0009 & 13.1 \\
Khot--Regev YES, $d=3$, $s_b=4$ & 12 & 2 & 160 & 382 & 2 & 2 & 1 & 1 & 0 & 1.0364 & 1.0182 & 10.6 \\
Khot--Regev YES, $d=3$, $s_b=8$ & 24 & 2 & 608 & 2\,938 & 2 & 2 & 0 & 2 & 0 & 1.0237 & 1.0149 & 11.2 \\
\midrule
\textbf{All} & & \textbf{44} & & & \textbf{44} & \textbf{26} & \textbf{18} & \textbf{8} & \textbf{18} & \textbf{2.2500} & \textbf{1.2095} & \textbf{209.7} \\
\bottomrule
\end{tabular}%
}
\end{table}
\subsection{Complements of the DIMACS clique benchmark}
\label{sec:dimacs}
The complements of the $68$ graphs of the DIMACS clique benchmark~\cite{johnson1996cliques}, in the form distributed with the NPBench collection~\cite{npbench}, were solved with \texttt{batch\_iris} on the folder \texttt{experiment/} of the repository, with the size option and logging; Table~\ref{tab:dimacs} reports the size of the returned independent dominating set and the time of \textsc{Siriaisa} recorded in the log. The optimum is not known for these instances, and no integer program was run. The time ranged from $0.028$\,s (\texttt{MANN\_a9}) to $11.9$\,s (\texttt{c-fat500-2}), with mean $3.47$\,s and total $236.0$\,s.
\begin{table}[H]
\centering
\scriptsize
\caption{Complements of the DIMACS clique benchmark graphs: size $|S|$ of the returned set and time of \textsc{Siriaisa} in seconds.}
\label{tab:dimacs}
\begin{tabular}{lrr@{\hspace{2em}}lrr}
\toprule
Instance & $|S|$ & Time & Instance & $|S|$ & Time \\
\midrule
\texttt{brock200\_1} & 8 & 1.01 & \texttt{brock200\_2} & 4 & 1.28 \\
\texttt{brock200\_3} & 5 & 1.07 & \texttt{brock200\_4} & 6 & 1.09 \\
\texttt{brock400\_1} & 10 & 1.66 & \texttt{brock400\_2} & 11 & 1.52 \\
\texttt{brock400\_3} & 11 & 1.54 & \texttt{brock400\_4} & 11 & 1.61 \\
\texttt{brock800\_1} & 8 & 7.39 & \texttt{brock800\_2} & 9 & 6.74 \\
\texttt{brock800\_3} & 9 & 7.11 & \texttt{brock800\_4} & 9 & 10.11 \\
\texttt{c-fat200-1} & 10 & 2.27 & \texttt{c-fat200-2} & 22 & 2.35 \\
\texttt{c-fat200-5} & 56 & 2.58 & \texttt{c-fat500-1} & 12 & 11.69 \\
\texttt{c-fat500-10} & 124 & 7.12 & \texttt{c-fat500-2} & 24 & 11.85 \\
\texttt{c-fat500-5} & 62 & 8.88 & \texttt{C1000.9} & 31 & 6.95 \\
\texttt{C125.9} & 14 & 3.50 & \texttt{C250.9} & 18 & 2.35 \\
\texttt{C500.9} & 25 & 2.87 & \texttt{gen200\_p0.9\_44} & 16 & 2.55 \\
\texttt{gen200\_p0.9\_55} & 16 & 2.82 & \texttt{gen400\_p0.9\_55} & 21 & 2.50 \\
\texttt{gen400\_p0.9\_65} & 22 & 2.53 & \texttt{gen400\_p0.9\_75} & 24 & 2.41 \\
\texttt{hamming10-2} & 128 & 5.12 & \texttt{hamming10-4} & 13 & 9.62 \\
\texttt{hamming6-2} & 12 & 1.74 & \texttt{hamming6-4} & 2 & 0.10 \\
\texttt{hamming8-2} & 32 & 4.48 & \texttt{hamming8-4} & 4 & 4.11 \\
\texttt{johnson16-2-4} & 8 & 3.09 & \texttt{johnson32-2-4} & 16 & 3.61 \\
\texttt{johnson8-2-4} & 4 & 1.13 & \texttt{johnson8-4-4} & 7 & 4.07 \\
\texttt{keller4} & 5 & 2.83 & \texttt{keller5} & 10 & 9.46 \\
\texttt{MANN\_a27} & 27 & 0.14 & \texttt{MANN\_a45} & 45 & 0.20 \\
\texttt{MANN\_a81} & 81 & 0.35 & \texttt{MANN\_a9} & 9 & 0.03 \\
\texttt{p\_hat1000-3} & 15 & 7.82 & \texttt{p\_hat300-1} & 3 & 2.09 \\
\texttt{p\_hat300-2} & 5 & 1.59 & \texttt{p\_hat300-3} & 10 & 1.13 \\
\texttt{p\_hat500-1} & 3 & 4.98 & \texttt{p\_hat500-2} & 7 & 3.96 \\
\texttt{p\_hat500-3} & 11 & 2.12 & \texttt{p\_hat700-1} & 3 & 9.54 \\
\texttt{p\_hat700-2} & 7 & 7.03 & \texttt{p\_hat700-3} & 14 & 3.97 \\
\texttt{san200\_0.7\_1} & 7 & 1.05 & \texttt{san200\_0.7\_2} & 6 & 1.23 \\
\texttt{san200\_0.9\_1} & 16 & 1.56 & \texttt{san200\_0.9\_2} & 16 & 1.48 \\
\texttt{san200\_0.9\_3} & 15 & 1.47 & \texttt{san400\_0.5\_1} & 4 & 2.64 \\
\texttt{san400\_0.7\_1} & 8 & 1.95 & \texttt{san400\_0.7\_2} & 8 & 2.03 \\
\texttt{san400\_0.7\_3} & 8 & 2.01 & \texttt{san400\_0.9\_1} & 22 & 1.43 \\
\texttt{sanr200\_0.7} & 7 & 1.06 & \texttt{sanr200\_0.9} & 16 & 1.45 \\
\texttt{sanr400\_0.5} & 5 & 2.78 & \texttt{sanr400\_0.7} & 9 & 2.25 \\
\bottomrule
\end{tabular}
\end{table}
\section{Conclusion}
\label{sec:conclusion}
\textsc{Siriaisa} 0.0.9 returns an independent dominating set (Theorem~\ref{thm:correctness}) in $O(n+m)$ expected time for the default parameters (Theorem~\ref{thm:runtime}). It combines twelve base strategies, five improvers and a refinement; the exact solver of the ensemble is a conditioned dynamic program on induced forests, which replaces the bipartite exact solvers of \textsc{Salvador} because MIDS is NP-complete on bipartite graphs. The output has ratio at most $\Delta$ (Corollary~\ref{cor:delta}), is optimal on forests (Theorem~\ref{thm:forest}), and has ratio at most $\sqrt n$ on the classes of Theorem~\ref{thm:sqrt}; the degree-splitting strategy yields a dominating set of size at most $\lfloor\sqrt n\rfloor(i(G)+s(G))$ on every graph, and the output satisfies the same bound when the decoded set is independent (Theorem~\ref{thm:split}); the excess $s(G)$ is largest on complete graphs, where the output is optimal, and it vanishes on the NP-hard and UG-hard families of bounded degree once $n\ge\Delta^2$ (Propositions~\ref{prop:sworst}, \ref{prop:complete} and~\ref{prop:families}). On cubic graphs, on which MIDS is APX-hard, $s(G)\le8$, with $s(G)=0$ for $n\ge10$, and the output has ratio at most $2$ (Proposition~\ref{prop:cubic} and Theorem~\ref{thm:regular}); on planar graphs with $n\ge400$, $s(G)<2\sqrt n+19$, and $K_{2,n-2}$ attains $s\ge2\sqrt n-3$ (Proposition~\ref{prop:planar}). On circle graphs, on which MIDS is not approximable within $n^{\varepsilon}$ for any $\varepsilon<1$ unless $\mathrm{P}=\mathrm{NP}$, $s(G)$ can be computed from a chord model in $O(n\log n)$ time and reaches its largest value $s(K_n)$ (Proposition~\ref{prop:circle}), and Conjecture~\ref{conj:sqrt} restricted to circle graphs would imply $\mathrm{P}=\mathrm{NP}$ (Corollary~\ref{cor:circle}). The graph of a formula with $t$ copies of every clause, $t$ at least the largest clause width $W$, has only independent dominating sets with $N$ vertices, the satisfying assignments, or with at least $t+N$ vertices (Theorem~\ref{thm:satgraph}), so that with $t=W$ every independent dominating set of ratio smaller than $1+W/N$ is a satisfying assignment (Corollary~\ref{cor:satratio}); it proves the inapproximability of MIDS within $n^{1-\varepsilon}$ for every $\varepsilon>0$ directly from satisfiability, without a gap from the PCP theorem (Theorem~\ref{thm:satinapprox}). On $10\,000$ structured and random graphs the output is optimal on $9\,999$; on $112$ bipartite graphs it is optimal on all $95$ instances with a proved optimum, and $17$ are open; on the instances of the reductions of Chleb{\'\i}k and Chleb{\'\i}kov{\'a} it is optimal on the $18$ SC-IDS instances and on $2$ of the $30$ VC-IDS instances with a proved optimum, and the vertex cover decoded on the Khot--Regev instances has ratio between $1.25$ and $1.8665$. In the experiments of Section~\ref{sec:splitexp}, the output is optimal on all $49$ cubic graphs with a proved optimum, on all $8$ planted perfect codes of degree up to $32$, on $34$ of the $38$ circle graphs with a proved optimum, and on $79$ of the $87$ instances of the hard and structured families with a proved optimum.
We do not claim that \textsc{Siriaisa} has ratio $O(\sqrt n)$ on every graph; this is Conjecture~\ref{conj:sqrt}, and a proof would imply $\mathrm{P}=\mathrm{NP}$ (Theorem~\ref{thm:sqrtpnp}). Nor do we claim any bound of the form of Theorem~\ref{thm:ugc} or Corollary~\ref{cor:aks}, which would refute UGC unless $\mathrm{P}=\mathrm{NP}$, and would imply $\mathrm{P}=\mathrm{NP}$ if the theorem reported in~\cite{openai2026ugc} holds. The implementation is freely available as the \texttt{siriaisa} package on PyPI~\cite{Vega26Siriaisa}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Acknowledgements}
The author would like to thank Iris, Marilin, Sonia, Yoselin, and Arelis for their support.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Statements and Declarations}
\subsection*{Declaration of interests}
The author declares no competing interests.
\subsection*{Funding sources}
This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.
\subsection*{Declaration of generative AI in scientific writing}
The author designed the strategies of \textsc{Siriaisa}, and used Claude Opus 5.5 to implement them by vibe coding, to write the experiment scripts of the folder \texttt{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.
\subsection*{Data availability}
Code and data: \url{https://github.com/frankvegadelgado/mids} (release \texttt{v0.0.9}); the experiments of Section~\ref{sec:experiments} are reproduced by running the scripts of \texttt{car/} and the command \texttt{batch\_iris} on the folder \texttt{experiment/}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{elsarticle-num}
\bibliography{biblio}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}