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

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 becomes an MIDS instance whose optimum is $\tau$ 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.8 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)\,\alpha_{\mathrm A}(n))$ for the default parameters, with $\alpha_{\mathrm A}$ the inverse Ackermann function (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 parametric bound $n^{1-\varepsilon}\,(i(G)+s_\varepsilon(G))$ for splitting at $\lfloor n^{1-\varepsilon}\rfloor$, $\varepsilon\in(0,1]$, with its consequences, among them the ratio $n^{3/4}$ on every graph with $\Delta\le\lfloor n^{3/4}\rfloor$ and $s_\varepsilon(K_n)\ge n$ for every fixed $\varepsilon$ and large $n$ (Theorem~\ref{thm:spliteps}, Corollary~\ref{cor:spliteps}).
\item The conjecture that the ratio is at most $n^{3/4}$ on every graph, with the theorem that a proof would imply $\mathrm{P}=\mathrm{NP}$ (Conjecture~\ref{conj:sqrt}, Theorem~\ref{thm:sqrtpnp}).
\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; $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.
\item The application to the SAT solver \texttt{satypy} 0.0.4 (Section~\ref{sec:sat}): the structure of the SAT-IDS graph, with $i=p$ on satisfiable and $i\ge\beta+p$ on unsatisfiable formulas (Lemma~\ref{lem:satids}), the least number of clause copies $\beta$ with $\beta+p>2p^2$ (Lemma~\ref{lem:sathat}) and with $\beta+p>2\sqrt n\,p$ (Lemma~\ref{lem:satbound}), the correctness of every answer except UNSATISFIABLE on a satisfiable formula, which requires a ratio larger than $2p$, the correctness of every answer when the ratio on the graph is at most $2p$ (Theorem~\ref{thm:sat}), the failure of the bound of Theorem~\ref{thm:split} to separate satisfiable from unsatisfiable formulas for every number of copies (Proposition~\ref{prop:nosep}), the exact branching on the clause named by the output (Proposition~\ref{prop:branch}), the gap $p$ against more than $p\,n^{1-1/t}$ with $\beta_t=p^t(3q)^{t-1}+1$ copies (Theorem~\ref{thm:satgap}), which gives a self-contained proof of Halld{\'o}rsson's theorem (Corollary~\ref{cor:inapprox}) and the decision of every formula under Conjecture~\ref{conj:sqrt} (Corollary~\ref{cor:sat}), the asymptotic $s(G)\sim2pL$ of the splitting excess with $\beta^*$ copies (Proposition~\ref{prop:satexcess}), and the identity $\mu(\varphi)=\lfloor i(G)/\beta\rfloor$ with the minimum number $\mu(\varphi)$ of falsified clauses (Theorem~\ref{thm:maxsat}); and, on every graph, the inequality $\lfloor\sqrt n\rfloor(i(G)+s(G))\ge n-i(G)$ (Proposition~\ref{prop:splitlower}).
\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 application to Boolean satisfiability, Section~\ref{sec:experiments} reports the experiments and Section~\ref{sec:conclusion} concludes.

\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.8. 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.8 \\
\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.8. ``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 $\delta(v)=0$ if $\mathrm{pre}(v)$ or some child attains $\mathrm{IN}(c)\le a(c)$, $\delta(v)=\min_c(\mathrm{IN}(c)-a(c))$ otherwise (one child is forced into $X$), and $\mathrm{DOM}(v)=\infty$ when no such child exists and $\neg\mathrm{pre}(v)$. A root $r$ takes $\min(\mathrm{IN}(r),\mathrm{DOM}(r),\mathrm{FREE}(r)+u(r))$, and back-pointers recover $X$.
\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. The rounds stop at a work budget of $40(n+m)$, and 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.
\begin{algorithm}[H]
\caption{\textsc{ForestLayers}$(\mathrm{adj})$}
\label{alg:layers}
\begin{algorithmic}[1]
\Require Index graph; layering budget $8(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 budget allows}
\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)|<P$, so a minimiser has no penalty: it is an independent dominating set of $F$, of minimum size.
\end{proof}

\begin{Theorem}[Correctness]
\label{thm:correctness}
For every finite undirected graph $G$, Algorithm~\ref{alg:main} returns an independent dominating set of $G$, and every candidate $c_1,\dots,c_{18}$ is an independent dominating set of $G$.
\end{Theorem}
\begin{proof}
Self-loops do not affect independence or domination of other vertices and are removed. $c_1$--$c_4$, $c_7$, $c_8$, $c_{13}$ and $c_{14}$ are outputs of Algorithm~\ref{alg:complete}, hence independent dominating sets by Lemma~\ref{lem:complete}. $c_5$, $c_6$ and $c_{12}$ select only vertices with no selected vertex in their closed neighbourhood and stop when every vertex is dominated, so they are maximal independent sets. In Algorithm~\ref{alg:layers} the vertices of a layer that are not yet dominated have no neighbour in $X$, the layer is an induced forest, and the forest solution is independent in $G$ (Lemma~\ref{lem:forestdp}), so $X$ stays independent; the final greedy completion adds only undominated vertices. \textsc{ResolveLayer} ($c_{10}$, $c_{11}$, \textsc{ForestLNS}) ends with Algorithm~\ref{alg:complete}. $c_{17}$ joins an independent set of forced vertices with an independent dominating set of the residual graph, which contains no neighbour of a forced vertex, and every vertex outside the residual graph is a forced vertex or one of its neighbours. In Algorithm~\ref{alg:improve} the descent inserts $u$ after removing all its neighbours in $S$ and refills only undominated vertices, so $S$ stays a maximal independent set, and the swap search records a set only when it has no undominated vertex and no conflicting edge. Finally, the implementation verifies every candidate explicitly and raises an error otherwise.
\end{proof}

\section{Runtime Analysis}
\label{sec:runtime}
Hash-table operations are counted as $O(1)$ expected time; they occur only in the relabelling of the input vertices, in the multigraph of $c_{11}$ and in the copy graph of $c_{13}$.

\begin{Lemma}[Copy graph]
\label{lem:copy}
In Algorithm~\ref{alg:split} let $B=\{v:\deg_G(v)>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)\,\alpha_{\mathrm A}(n))$ 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 union by size and path halving, $O(\alpha_{\mathrm A}(n))$ amortised per operation~\cite{tarjan1975efficiency}, within the work budgets $40(n+m)$ and $8(n+m)$, 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)\,\alpha_{\mathrm A}(n))$.
\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 first round of $c_1$ fits in its budget, since its cost $4(n+2m)$ plus the initial $n+m$ is at most $40(n+m)$; the maximum spanning forest is $G$ itself, the forest optimum is independent in $G$ and is kept entirely, and it dominates $G$, so the residual graph is empty and $c_1$ is the forest optimum of Lemma~\ref{lem:forestdp}. Every candidate after $c_1$ 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_1|=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|$, domination, and $c_{13}\le|S_0|$ when $S_0$ is independent; the output is no larger than $c_{13}$.
\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<n-1=(\sqrt n-1)(\sqrt n+1)$, $(n-2)/k<\sqrt n+1$. (iii) $\lceil d/k\rceil$ is non-decreasing in $d$, every degree is at most $n-1$ and $|B|\le n$; in $K_n$ every vertex has degree $n-1>\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}[Lower bound of the splitting bound]
\label{prop:splitlower}
For every graph $G$ on $n$ vertices and $k=\max(1,\lfloor\sqrt n\rfloor)$, $k\,(i(G)+s(G))\ge n-i(G)$. In particular the bound of Theorem~\ref{thm:split} is at least $n-i(G)$ on every graph.
\end{Proposition}
\begin{proof}
Let $D$ be a minimum independent dominating set. It dominates the other $n-i(G)$ vertices, so $\sum_{d\in D}\deg(d)\ge n-i(G)$. A vertex $d\in D\cap B$ contributes $\lceil\deg(d)/k\rceil-1\ge\deg(d)/k-1$ to $s(G)$, and a vertex $d\in D\setminus B$ satisfies $\deg(d)\le k$, so $\deg(d)/k-1\le0$; since every term of $s(G)$ is non-negative, $s(G)\ge\sum_{d\in D}(\deg(d)/k-1)\ge(n-i(G))/k-i(G)$. Multiplying by $k$ gives $k\,s(G)\ge n-i(G)-k\,i(G)$.
\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 $2<t$, so $b_1$ is selected and dominates the rest; $c_3\cap C=\{a_1,b_1\}$, and no single vertex dominates $C$, so $i(C)=2$. \emph{Wheel} (a hub joined to a cycle): the hub has the largest gain $|C|$ and dominates $C$, so $c_3\cap C$ is the hub and $i(C)=1$. \emph{Double star} (adjacent hubs $x$, $y$ with $a\ge b\ge1$ leaves): $x$ has the largest gain $a+2$; selecting it dominates its leaves and $y$, and the $b$ leaves of $y$ are then selected, so $|c_3\cap C|=1+b$. An independent dominating set contains $x$ (and then all leaves of $y$), or $y$ (and all leaves of $x$), or neither (and all $a+b$ leaves), so $i(C)=1+\min(a,b)=1+b$.
\end{proof}

By Propositions~\ref{prop:sworst} and~\ref{prop:complete}, the bound $\lfloor\sqrt n\rfloor\,(i(G)+s(G))$ of Theorem~\ref{thm:split} is weakest on complete graphs, where $s(G)$ is of order $n^{3/2}$ and $i(G)=1$, and on balanced complete bipartite graphs, where $s(G)$ is of order $n^{3/2}/2$; on both, $i(G)$ is attained by the greedy strategy $c_3$ and the output is optimal. The bound is useful when few vertices have degree larger than $\sqrt n$.
\begin{Corollary}[Few vertices of large degree]
\label{cor:fewhigh}
If $|B|\le i(G)/(\sqrt n+1)$, in particular if $|B|\,(\sqrt n+1)(\Delta+1)\le n$, then $s(G)\le i(G)$, and the decoded set $S_0$ of Theorem~\ref{thm:split} has at most $2\lfloor\sqrt n\rfloor\,i(G)$ vertices; if $S_0$ is independent, the output has ratio at most $2\sqrt n$.
\end{Corollary}
\begin{proof}
By Proposition~\ref{prop:sworst}(ii), $s(G)\le|B|(\sqrt n+1)\le i(G)$, and $i(G)\ge n/(\Delta+1)$ by Lemma~\ref{lem:mis}. Theorem~\ref{thm:split} gives the rest.
\end{proof}

Algorithm~\ref{alg:split} is defined for every block size $k\ge1$. For $\varepsilon\in(0,1]$, let \textsc{DegreeSplit}$_\varepsilon$ denote Algorithm~\ref{alg:split} with $k_\varepsilon=\max(1,\lfloor n^{1-\varepsilon}\rfloor)$ in place of $\max(1,\lfloor\sqrt n\rfloor)$, let $B_\varepsilon=\{v:\deg_G(v)>k_\varepsilon\}$, and define
\[
s_\varepsilon(G)=\sum_{v\in B_\varepsilon}\Bigl(\Bigl\lceil\frac{\deg_G(v)}{k_\varepsilon}\Bigr\rceil-1\Bigr).
\]
Strategy $c_{13}$ is \textsc{DegreeSplit}$_{1/2}$, with $k_{1/2}=k$ and $s_{1/2}(G)=s(G)$.
\begin{Theorem}[Parametric degree splitting]
\label{thm:spliteps}
Let $\varepsilon\in(0,1]$. For each inner solver of \textsc{DegreeSplit}$_\varepsilon$, the decoded set $S_0$ is a dominating set of $G$ with
\[
|S_0|\ \le\ k_\varepsilon\,\bigl(i(G)+s_\varepsilon(G)\bigr)\ \le\ n^{1-\varepsilon}\,\bigl(i(G)+s_\varepsilon(G)\bigr).
\]
If $S_0$ is independent in $G$ for one of the inner solvers, then the set $S_\varepsilon$ returned by \textsc{DegreeSplit}$_\varepsilon$ is an independent dominating set of $G$ with $|S_\varepsilon|\le k_\varepsilon\,(i(G)+s_\varepsilon(G))$. For $\varepsilon=\frac12$ this is Theorem~\ref{thm:split}.
\end{Theorem}
\begin{proof}
The statements and proofs of Lemmas~\ref{lem:copy}, \ref{lem:lift} and~\ref{lem:decode-split} use only that $k$ is a positive integer, so they hold with $k_\varepsilon$, $B_\varepsilon$ and $s_\varepsilon(G)$ in place of $k$, $B$ and $s(G)$: the copy graph $H_\varepsilon$ has maximum degree at most $k_\varepsilon$, $i(H_\varepsilon)\le i(G)+s_\varepsilon(G)$, and decoding gives a dominating set $S_0$ with $|S_0|\le|S_H|$. Every inner solver returns a maximal independent set $S_H$ of $H_\varepsilon$, and Lemma~\ref{lem:mis}, applied componentwise with $\max(1,\Delta(H_\varepsilon))\le k_\varepsilon$, gives $|S_H|\le k_\varepsilon\,i(H_\varepsilon)$. Finally $k_\varepsilon\le n^{1-\varepsilon}$, since $n^{1-\varepsilon}\ge1$ for $n\ge1$. If $S_0$ is independent, Algorithm~\ref{alg:complete} returns $S_0$ (Lemma~\ref{lem:decode-split}), and $S_\varepsilon$ is the smallest of the repaired sets, each an independent dominating set by Lemma~\ref{lem:complete}.
\end{proof}

\begin{Corollary}[Consequences of Theorem~\ref{thm:spliteps}]
\label{cor:spliteps}
Let $G$ be a graph on $n\ge1$ vertices with $m$ edges, and let $\varepsilon\in(0,1]$.
\begin{enumerate}
\item[(i)] \emph{Monotonicity.} If $0<\varepsilon'\le\varepsilon$, then $k_{\varepsilon'}\ge k_\varepsilon$, $B_{\varepsilon'}\subseteq B_\varepsilon$ and $s_{\varepsilon'}(G)\le s_\varepsilon(G)$.
\item[(ii)] \emph{Weighted excess.} $\sum_{v\in B_\varepsilon}(\deg(v)-k_\varepsilon)\le k_\varepsilon\,s_\varepsilon(G)\le\sum_{v\in B_\varepsilon}(\deg(v)-1)\le2m-|B_\varepsilon|$; hence the bound of Theorem~\ref{thm:spliteps} satisfies $k_\varepsilon\,(i(G)+s_\varepsilon(G))\le k_\varepsilon\,i(G)+2m-|B_\varepsilon|$.
\item[(iii)] \emph{Lower bound.} $k_\varepsilon\,(i(G)+s_\varepsilon(G))\ge n-i(G)$.
\item[(iv)] \emph{Vanishing excess.} $s_\varepsilon(G)=0$ if and only if $\Delta\le k_\varepsilon$, and then $k_\varepsilon\,(i(G)+s_\varepsilon(G))=k_\varepsilon\,i(G)\ge\max(1,\Delta)\,i(G)$. If $\varepsilon<1$ and $\Delta\le D$ for an integer $D\ge1$, then $s_\varepsilon(G)=0$ for every $n\ge D^{1/(1-\varepsilon)}$; in particular $s_{1/4}(G)=0$ for every $n\ge D^{4/3}$, and on every cubic graph with $n\ge6$.
\item[(v)] \emph{Ratio $n^{1-\varepsilon}$.} If $s_\varepsilon(G)=0$, the output $S$ of Algorithm~\ref{alg:main} satisfies $|S|/i(G)\le n^{1-\varepsilon}$; in particular Conjecture~\ref{conj:sqrt} holds on every graph with $\Delta\le\lfloor n^{3/4}\rfloor$.
\item[(vi)] \emph{Bounded excess.} If $s_\varepsilon(G)\le i(G)$, then $|S_0|\le2k_\varepsilon\,i(G)\le2n^{1-\varepsilon}\,i(G)$ for every inner solver of \textsc{DegreeSplit}$_\varepsilon$, and $|S_\varepsilon|\le2n^{1-\varepsilon}\,i(G)$ when $S_0$ is independent.
\item[(vii)] \emph{Complete graphs.} For $n\ge2$, $s_\varepsilon(K_n)=n\,(\lceil(n-1)/k_\varepsilon\rceil-1)$, which is $0$ if $k_\varepsilon\ge n-1$ and at least $n$ otherwise; for every fixed $\varepsilon\in(0,1]$ there is $n_0$ such that $s_\varepsilon(K_n)\ge n$ for every $n\ge n_0$. On $K_n$ the output of Algorithm~\ref{alg:main} is optimal.
\end{enumerate}
\end{Corollary}
\begin{proof}
(i) $n^{1-\varepsilon'}\ge n^{1-\varepsilon}$ for $n\ge1$, so $k_{\varepsilon'}\ge k_\varepsilon$; a vertex of degree larger than $k_{\varepsilon'}$ has degree larger than $k_\varepsilon$, and $\lceil d/k\rceil$ is non-increasing in $k$, so every term of $s_{\varepsilon'}(G)$ is at most the corresponding term of $s_\varepsilon(G)$, and the terms are non-negative. (ii) For integers $d,k\ge1$, $d/k\le\lceil d/k\rceil\le(d-1)/k+1$, so $d-k\le k(\lceil d/k\rceil-1)\le d-1$; summing over $B_\varepsilon$ and using $\sum_{v\in B_\varepsilon}\deg(v)\le2m$ gives the inequalities. (iii) The proof of Proposition~\ref{prop:splitlower} uses only that $k$ is a positive integer, and applies with $k_\varepsilon$, $B_\varepsilon$ and $s_\varepsilon(G)$. (iv) $\lceil d/k_\varepsilon\rceil-1=0$ exactly when $d\le k_\varepsilon$, so $s_\varepsilon(G)=0$ if and only if $B_\varepsilon=\emptyset$, that is $\Delta\le k_\varepsilon$; then $k_\varepsilon\ge\max(1,\Delta)$. For an integer $D\ge1$, $\lfloor n^{1-\varepsilon}\rfloor\ge D$ if and only if $n^{1-\varepsilon}\ge D$, that is $n\ge D^{1/(1-\varepsilon)}$, and then $k_\varepsilon\ge D\ge\Delta$. For $\varepsilon=\frac14$ the exponent is $\frac43$; a cubic graph has even $n\ge4$, and $\lfloor6^{3/4}\rfloor=3$, so $k_{1/4}\ge3=\Delta$ for $n\ge6$. (v) By (iv), $\max(1,\Delta)\le k_\varepsilon\le n^{1-\varepsilon}$, and Corollary~\ref{cor:delta} gives $|S|\le\max(1,\Delta)\,i(G)$. For $\varepsilon=\frac14$, $\Delta\le\lfloor n^{3/4}\rfloor$ gives $\max(1,\Delta)\le n^{3/4}$ for $n\ge1$. (vi) Theorem~\ref{thm:spliteps} with $i(G)+s_\varepsilon(G)\le2i(G)$. (vii) Every vertex of $K_n$ has degree $n-1$. If $k_\varepsilon\ge n-1$, then $B_\varepsilon=\emptyset$; otherwise every vertex lies in $B_\varepsilon$ and $\lceil(n-1)/k_\varepsilon\rceil\ge2$, so every vertex contributes at least $1$. For fixed $\varepsilon>0$, $n^{1-\varepsilon}/(n-1)\to0$, so $k_\varepsilon\le n^{1-\varepsilon}<n-1$ for every $n$ large enough. Optimality is Proposition~\ref{prop:complete}.
\end{proof}

\paragraph{The splitting excess on hard families} Proposition~\ref{prop:families} and Table~\ref{tab:sfamilies} give $s(G)$ on the families on which MIDS is NP-hard, NP-hard to approximate, or on which, through the VC-IDS reduction of Section~\ref{sec:hardness}, it encodes a UG-hard vertex cover problem, and on further structured families.
\begin{Proposition}[Splitting excess on graph families]
\label{prop:families}
Let $k=\lfloor\sqrt n\rfloor$.
\begin{enumerate}
\item[(a)] \emph{Bounded degree.} If $\Delta\le D$ for a constant $D$, then $s(G)=0$ for every $n\ge D^2$. This holds for cubic graphs with $n\ge10$ (Proposition~\ref{prop:cubic}); for graphs and bipartite graphs of maximum degree at most $B$ with $n\ge B^2$; for the SC-IDS graphs of maximum degree $B$ with $n\ge B^2$; for $h(H)$ with $\Delta(H)\le D$ and $|V(H)|+6|E(H)|\ge\max(D,3)^2$; for graphs of maximum degree $d$ with $n\ge d^2$, the setting of~\cite{austrin2011inapproximability}; for grids with $n\ge16$; and for hypercubes $Q_q$ with $q\ge4$.
\item[(b)] \emph{Khot--Regev graphs.} The YES graph with $N$ blocks of $s_b$ subsets on a $d$-regular constraint graph has $n=Ns_b$ vertices and maximum degree at most $ds_b$, so $s(G)\le n(\lceil ds_b/k\rceil-1)$, and $s(G)=0$ when $N\ge d^2s_b$.
\item[(c)] \emph{Sparse graphs.} $s(G)\le2m/k$; for planar graphs $s(G)\le(6n-12)/k$, for bipartite planar graphs $s(G)\le(4n-8)/k$ (sharper bounds in Proposition~\ref{prop:planar}), and for graphs with $m\le cn$, $s(G)\le2c\,n/k\le2c(\sqrt n+2)$ for $n\ge4$.
\item[(d)] \emph{Sparse random graphs.} For a constant $c>0$, 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<n/(\sqrt n-1)=\sqrt n+1+1/(\sqrt n-1)\le\sqrt n+2$ for $n\ge4$. (d) For $t=k+1>\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)<D^2(D-1)$, and $s(G)=0$ for every $n\ge D^2$.
\end{enumerate}
\end{Proposition}
\begin{proof}
(i) A cubic graph has an even number $n\ge4$ of vertices, since $3n=2m$. For $n\in\{4,6,8\}$, $k=2$, every vertex has degree $3>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 $n<D^2$, every vertex contributes $\lceil\deg(v)/k\rceil-1\le D-1$, since $k\ge1$, so $s(G)\le n(D-1)<D^2(D-1)$.
\end{proof}

On a cubic graph with $n\ge10$, Algorithm~\ref{alg:split} therefore splits no vertex, $H=G$, and $c_{13}$ applies its inner solvers to $G$ itself. The ratio of the output on cubic graphs is bounded by the regularity of the graph.
\begin{Theorem}[Regular graphs]
\label{thm:regular}
If $G$ is $d$-regular with $d\ge1$, every independent dominating set $S$ of $G$, in particular the output of Algorithm~\ref{alg:main}, satisfies $|S|\le n/2$ and $|S|/i(G)\le(d+1)/2$. On cubic graphs, $n/4\le i(G)\le|S|\le n/2$ and the ratio is at most $2$.
\end{Theorem}
\begin{proof}
Let $I$ be an independent set of $G$. Every vertex of $I$ has its $d$ neighbours in $V\setminus I$, and every vertex of $V\setminus I$ has at most $d$ neighbours in $I$, so counting the edges between $I$ and $V\setminus I$ gives $d|I|\le d(n-|I|)$, that is $|I|\le n/2$. The output is an independent dominating set (Theorem~\ref{thm:correctness}), and Lemma~\ref{lem:mis} gives $i(G)\ge n/(d+1)$, so $|S|/i(G)\le(n/2)/(n/(d+1))=(d+1)/2$. For $d=3$, $n/4\le i(G)$ and $(d+1)/2=2$.
\end{proof}

\paragraph{Planar graphs} MIDS is NP-hard on cubic planar graphs~\cite{manlove1999algorithmic} and NP-complete on cubic planar bipartite graphs~\cite{loverov2020np}, hence on planar and on bipartite planar graphs. On planar graphs the splitting excess is not bounded by a constant, but it is at most $2\sqrt n+O(1)$, and the leading constant $2$ is attained.
\begin{Proposition}[Splitting excess on planar graphs]
\label{prop:planar}
Let $G$ be a planar graph on $n$ vertices, $k=\lfloor\sqrt n\rfloor$, $B=\{v:\deg(v)>k\}$ 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_v<b_v$; two chords cross if and only if exactly one endpoint of one of them lies strictly between the endpoints of the other.
\begin{Proposition}[Splitting excess on circle graphs]
\label{prop:circle}
\begin{enumerate}
\item[(i)] For a circle graph given by a chord model, $\deg(v)=b_v-a_v-1-2\,|\{u:a_v<a_u<b_u<b_v\}|$ for every chord $v$, so all degrees, $B$ and $s(G)$ can be computed in $O(n\log n)$ time from the model, without listing the edges.
\item[(ii)] For every $n\ge3$, the complete graph $K_n$ and every complete bipartite graph $K_{a,b}$ with $a+b=n$ are circle graphs; hence the largest splitting excess among circle graphs on $n$ vertices equals the largest one among all graphs, $s(K_n)=n(\lceil(n-1)/k\rceil-1)\ge n^{3/2}-n-\sqrt n$, and on these graphs the output of Algorithm~\ref{alg:main} is optimal.
\end{enumerate}
\end{Proposition}
\begin{proof}
(i) The other $2n-2$ endpoints are distinct, and $b_v-a_v-1$ of them lie strictly between $a_v$ and $b_v$. A chord with both endpoints there does not cross $v$ and contributes two of them, a chord with exactly one endpoint there crosses $v$ and contributes one, and the other chords contribute none and do not cross $v$; this gives the formula. The numbers $|\{u:a_v<a_u<b_u<b_v\}|$ are counted for all $v$ by scanning the chords by decreasing $a_v$ and querying and updating a Fenwick tree over the right endpoints, in $O(n\log n)$ time; $B$ and $s(G)$ then take $O(n)$ time. (ii) The $n$ diameters of a regular $2n$-gon cross pairwise, so $K_n$ is a circle graph. For $K_{a,b}$, take $a$ horizontal and $b$ vertical chords of the unit circle, all at distance less than $\frac12$ from the centre: chords of the same direction are disjoint, and every horizontal chord crosses every vertical one. Proposition~\ref{prop:sworst}(iii) gives the value of $s(K_n)$ and its maximality, and Proposition~\ref{prop:complete} the optimality.
\end{proof}

\begin{Conjecture}[Ratio $n^{1-\varepsilon}$ with $\varepsilon=\frac14$]
\label{conj:sqrt}
For every graph $G$ on $n$ vertices, the output $S$ of Algorithm~\ref{alg:main} satisfies $|S|/i(G)\le n^{3/4}$.
\end{Conjecture}
Since $\sqrt n\le n^{3/4}$ for every $n\ge1$ and $2\sqrt n\le n^{3/4}$ for every $n\ge16$, Theorems~\ref{thm:sqrt} and~\ref{thm:split}, Corollary~\ref{cor:fewhigh} and Proposition~\ref{prop:complete} show that Conjecture~\ref{conj:sqrt} holds on every graph with $\Delta\le\sqrt n$, with $i(G)\ge\sqrt n$, or with $\alpha(G)\le\sqrt n\,i(G)$, on every graph with $n\ge16$, $s(G)\le i(G)$ and an independent decoded set, and on every graph whose components are complete multipartite, crown, wheel or double-star graphs.
\begin{Theorem}[Conditional consequence of Conjecture~\ref{conj:sqrt}]
\label{thm:sqrtpnp}
If Conjecture~\ref{conj:sqrt} is proved, then $\mathrm{P}=\mathrm{NP}$.
\end{Theorem}
\begin{proof}
Algorithm~\ref{alg:main} runs in polynomial time (Theorem~\ref{thm:runtime}), so Conjecture~\ref{conj:sqrt} would give a polynomial-time approximation of MIDS within $n^{1-\varepsilon}$ with $\varepsilon=\frac14$, which is impossible unless $\mathrm{P}=\mathrm{NP}$~\cite{halldorsson1993approximating} (see also Corollary~\ref{cor:inapprox}).
\end{proof}

\begin{Corollary}[Circle graphs]
\label{cor:circle}
If Conjecture~\ref{conj:sqrt} is proved for circle graphs only, then $\mathrm{P}=\mathrm{NP}$.
\end{Corollary}
\begin{proof}
Algorithm~\ref{alg:main} takes the graph and needs no chord model, and it runs in polynomial time (Theorem~\ref{thm:runtime}). The conjecture on circle graphs would give a polynomial-time approximation of MIDS on circle graphs within $n^{\varepsilon}$ with $\varepsilon=\frac34<1$, which is impossible unless $\mathrm{P}=\mathrm{NP}$~\cite{damian1999hardness}.
\end{proof}

\section{Hard Instances and the Unique Games Conjecture}
\label{sec:hardness}
Chleb{\'\i}k and Chleb{\'\i}kov{\'a} prove their bounded-degree results with two reductions~\cite{chlebik2008approximation}, which we use as instance generators.

\paragraph{SC-IDS} For a set system $\mathcal S$ over a universe $\mathcal U$, take the bipartite incidence graph of $\mathcal S$ and $\mathcal U$ and attach to every set node $S$ a path $S$--$S'$--$S''$. The graph is bipartite, its maximum degree is the largest of the set sizes plus one and the element frequencies, and $i=\mathrm{sc}(\mathcal S)+|\mathcal S|$, where $\mathrm{sc}$ is the minimum set cover size~\cite{chlebik2008approximation}.

\paragraph{VC-IDS} For a graph $H$ with $m_H$ edges, replace every edge $uv$ by the gadget of Figure~\ref{fig:gadget}: six new vertices $a,b,c,d,x,y$ and the eight edges $ua,ab,bc,cd,dv,bx,xy,yc$. The graph $h(H)$ has $|V(H)|+6m_H$ vertices, $8m_H$ edges and maximum degree $\max(\Delta(H),3)$. Chleb{\'\i}k and Chleb{\'\i}kov{\'a} use an edge gadget with these parameters and the identity of Proposition~\ref{prop:vcids}~\cite{chlebik2008approximation}; we prove the identity for the gadget of Figure~\ref{fig:gadget}.

\begin{figure}[H]
\centering
\begin{tikzpicture}[every node/.style={circle,draw,inner sep=1.5pt,minimum size=16pt,font=\small}]
\node (u) at (0,0) {$u$};
\node (a) at (1.5,0) {$a$};
\node (b) at (3,0) {$b$};
\node (c) at (4.5,0) {$c$};
\node (d) at (6,0) {$d$};
\node (v) at (7.5,0) {$v$};
\node (x) at (3,1.4) {$x$};
\node (y) at (4.5,1.4) {$y$};
\draw (u)--(a)--(b)--(c)--(d)--(v);
\draw (b)--(x)--(y)--(c);
\end{tikzpicture}
\caption{The edge gadget of the VC-IDS reduction: the edge $uv$ of $H$ is replaced by the path $u$--$a$--$b$--$c$--$d$--$v$ and the square $b$--$x$--$y$--$c$.}
\label{fig:gadget}
\end{figure}

\begin{Proposition}[VC-IDS identity]
\label{prop:vcids}
For every graph $H$ without isolated vertices and with $m_H$ edges, $i(h(H))=\tau(H)+2m_H$.
\end{Proposition}
\begin{proof}
Let $D$ be an independent dominating set of $h(H)$ and fix the gadget of an edge $uv$. The vertex $x$ is dominated only from $\{b,x,y\}$ and $y$ only from $\{x,y,c\}$; since $b$ and $c$ are adjacent, $D$ cannot dominate both without containing $x$ or $y$, and since $x$ and $y$ are adjacent, $D$ contains exactly one of them. Suppose $x\in D$ (the case $y\in D$ is symmetric, with $u,a,b$ and $v,d,c$ exchanged). Then $b,y\notin D$, so $c$ is dominated only from $\{c,d\}$ and $D$ contains $c$ or $d$; and $a$ is dominated only from $\{u,a\}$, so $D$ contains $a$ when $u\notin D$. Hence $D$ meets the gadget in at least $2$ vertices, and in at least $3$ when neither $u$ nor $v$ is in $D$. Let $X=D\cap V(H)$ and let $q$ be the number of edges of $H$ with no endpoint in $X$; then $|D|\ge|X|+2m_H+q$. Adding one endpoint of each of these $q$ edges to $X$ gives a vertex cover of $H$, so $|D|\ge\tau(H)+2m_H$. Conversely, for a minimum vertex cover $C$ of $H$, take $C$ and, in every gadget, $\{a,y\}$ if only $v\in C$, $\{d,x\}$ if only $u\in C$, and $\{x,c\}$ if $u,v\in C$. The set is independent and dominates every gadget vertex; a vertex $u\notin C$ has an edge, every edge at $u$ has its other endpoint in $C$, and the corresponding gadget contains the neighbour $a$ or $d$ of $u$, so $u$ is dominated. The set has $\tau(H)+2m_H$ vertices.
\end{proof}

\begin{Lemma}[Decoding a vertex cover]
\label{lem:decode}
For every independent dominating set $D$ of $h(H)$, the set $C_D$ formed by $D\cap V(H)$ and one endpoint of every edge of $H$ with no endpoint in $D$ is a vertex cover of $H$ with $|C_D|\le|D|-2m_H$, computable in $O(|V(H)|+m_H)$ time.
\end{Lemma}
\begin{proof}
This is the inequality $|D|\ge|X|+2m_H+q$ of the proof of Proposition~\ref{prop:vcids}.
\end{proof}

\begin{Theorem}[Conditional consequence for vertex cover]
\label{thm:ugc}
Assume that for every fixed $\varepsilon_0>0$ 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{Application to Boolean Satisfiability}
\label{sec:sat}
The SAT solver \texttt{satypy} 0.0.4~\cite{Vega26Satypy} decides a formula in conjunctive normal form in three stages: unit propagation and pure literal elimination, which answers UNSATISFIABLE on a conflict and otherwise commits literals and leaves a residual formula; an exact implication-graph solver when every residual clause has at most two literals; and otherwise a reduction of the residual formula to MIDS, solved by \textsc{Siriaisa} 0.0.8. Every SATISFIABLE answer is returned with an assignment, formed by the committed literals and the decoded literals, that is checked against every clause of the input formula. This section describes the third stage. Let $\varphi$ be the residual formula, with $p$ variables $x_1,\dots,x_p$ and $q$ clauses $C_1,\dots,C_q$, every clause a nonempty set of literals with no complementary pair.

\begin{Definition}[SAT-IDS graph]
\label{def:satids}
For an integer $\beta\ge1$, the graph $G_\beta(\varphi)$ has a \emph{literal vertex} for each of the $2p$ literals $x_r,\neg x_r$ and $\beta$ \emph{clause vertices} $c_{j,1},\dots,c_{j,\beta}$ for each clause $C_j$; its edges are $x_r\neg x_r$ for every variable and $c_{j,t}\ell$ for every clause $C_j$, every $t\le\beta$ and every literal $\ell\in C_j$. It has $n=2p+q\beta$ vertices and $p+\beta\sum_j|C_j|$ edges.
\end{Definition}

\begin{Lemma}[Structure of the SAT-IDS graph]
\label{lem:satids}
Let $\beta\ge p$ and let $D$ be an independent dominating set of $G=G_\beta(\varphi)$.
\begin{enumerate}
\item[(i)] If $D$ contains no clause vertex, then $D$ contains exactly one of $x_r$ and $\neg x_r$ for every $r$, $|D|=p$, and the literals of $D$ form a satisfying assignment of $\varphi$.
\item[(ii)] If $D$ contains a clause vertex $c_{j,t}$, then $D$ contains $c_{j,1},\dots,c_{j,\beta}$.
\item[(iii)] If $D$ contains a clause vertex, then $|D|\ge\beta+p$.
\item[(iv)] $i(G)=p$ if $\varphi$ is satisfiable, and $i(G)\ge\beta+p$ otherwise; no independent dominating set of $G$ has a size strictly between $p$ and $\beta+p$.
\item[(v)] If an assignment of $\varphi$ falsifies exactly one clause, then $i(G)\le\beta+p$; in particular $i(G)=\beta+p$ when $\varphi$ is unsatisfiable and such an assignment exists.
\end{enumerate}
\end{Lemma}
\begin{proof}
(i) The neighbours of $x_r$ and $\neg x_r$ are each other and clause vertices, none of which lies in $D$, so $D$ contains one of them, and not both since $D$ is independent. Hence $D$ consists of $p$ literal vertices, one per variable, which form an assignment; every clause vertex $c_{j,t}\notin D$ has a neighbour in $D$, a literal of $C_j$ set true. (ii) The neighbours of $c_{j,t}$ are the literals of $C_j$, so none of them lies in $D$; every $c_{j,s}$ has the same neighbours, so it is dominated only by itself and lies in $D$. (iii) If $D$ contains clause vertices of two clauses, then $|D|\ge2\beta\ge\beta+p$ by (ii). Otherwise $D$ contains the $\beta$ clause vertices of exactly one clause $C_j$. For every variable $x_r$, $C_j$ contains at most one of $x_r$ and $\neg x_r$; let $y$ be one that $C_j$ does not contain. The neighbours of $y$ are its complement and clause vertices of clauses other than $C_j$, which are not in $D$; so if neither $x_r$ nor $\neg x_r$ lies in $D$, then $y$ is not dominated. Hence $D$ contains a literal vertex of every variable and $|D|\ge\beta+p$. (iv) A satisfying assignment, as a set of $p$ literal vertices, is independent and dominates the complementary literals and every clause vertex, and by (i) and (iii) every independent dominating set has $p$ or at least $\beta+p$ vertices; if $\varphi$ is unsatisfiable, (i) excludes the first case. (v) Let the assignment $\sigma$ falsify only $C_j$, and let $D$ be the $p$ literals of $\sigma$ together with $c_{j,1},\dots,c_{j,\beta}$. The neighbours of $c_{j,t}$ are the literals of $C_j$, all false, so $D$ is independent; the false literals are dominated by their complements, and the clause vertices of the other clauses by a true literal. So $|D|=\beta+p$, and (iv) gives the equality.
\end{proof}

\begin{Lemma}[Number of copies]
\label{lem:satbound}
For integers $p,q\ge1$, let $\Lambda=4q^2p^4+8p^3-4qp^3$ and $\beta^*=2qp^2+\lfloor\sqrt\Lambda\rfloor+1-p$. Then $\beta^*$ is the least positive integer $\beta$ with $\beta+p>2p\sqrt{2p+q\beta}$. Moreover $p\le\beta^*\le4qp^2+1$.
\end{Lemma}
\begin{proof}
Write $C=\beta+p$, so that $2p+q\beta=qC+2p-qp>0$. Both sides of the inequality are positive, so it is equivalent to $f(C)=C^2-4qp^2C-(8p^3-4qp^3)>0$. The discriminant of $f$ is $4\Lambda$ with $\Lambda=4p^3(q^2p+2-q)>0$, since $q^2p\ge q$, so $f$ has the real roots $r_{1,2}=2qp^2\mp\sqrt\Lambda$. Since $f(p)=p^2-8p^3<0$, $r_1<p<r_2$, and every $C\ge p+1$ satisfies $f(C)>0$ if and only if $C>r_2$. As $2qp^2$ is an integer, the least integer larger than $r_2$ is $2qp^2+\lfloor\sqrt\Lambda\rfloor+1$, which gives $\beta^*$. Since $\Lambda\ge0$, $\beta^*\ge2qp^2+1-p\ge p$. If $q\ge2$, then $\Lambda\le4q^2p^4$ and $\beta^*\le4qp^2+1-p$; if $q=1$, then $\Lambda=4p^4+4p^3<(2p^2+p)^2$ and $\beta^*\le4p^2+1$.
\end{proof}
\begin{Lemma}[Copies for the ratio $2p$]
\label{lem:sathat}
For an integer $p\ge1$, let $\hat\beta=2p^2-p+1$. Then $\hat\beta$ is the least integer $\beta$ with $\beta+p>2p^2$, $\hat\beta\ge p+1$, and $G_{\hat\beta}(\varphi)$ has $n=2p+q\hat\beta\le2p+2qp^2$ vertices and $p+\hat\beta\sum_j|C_j|$ edges.
\end{Lemma}
\begin{proof}
For an integer $\beta$, $\beta+p>2p^2$ if and only if $\beta\ge2p^2-p+1$. Moreover $\hat\beta-(p+1)=2p(p-1)\ge0$, and the counts follow from Definition~\ref{def:satids}.
\end{proof}


For a literal $\ell$ of $\varphi$, let $o_\ell$ be the number of clauses that contain $\ell$, let $L=\sum_j|C_j|=\sum_\ell o_\ell$ be the number of literal occurrences of $\varphi$, and let $\lambda$ be the number of literals with $o_\ell\ge1$, so that $\lambda\le2p$.
\begin{Proposition}[Splitting excess of the SAT-IDS graph]
\label{prop:satexcess}
Let $\beta=\beta^*$, $G=G_\beta(\varphi)$ with $n$ vertices and $k=\lfloor\sqrt n\rfloor$.
\begin{enumerate}
\item[(i)] $k\ge qp$; the vertices of degree larger than $k$ are exactly the literal vertices $\ell$ with $o_\ell\ge1$, the literal vertex $\ell$ has degree $1+\beta o_\ell$, and $s(G)=\sum_{\ell:\,o_\ell\ge1}\bigl(\lceil(1+\beta o_\ell)/k\rceil-1\bigr)$.
\item[(ii)] $2pL-pL/k-\lambda<s(G)<2pL+((p+1)L+\lambda)/k$; hence
\[
1-\frac1{2k}-\frac1L\ <\ \frac{s(G)}{2pL}\ <\ 1+\frac1k\Bigl(1+\frac1L\Bigr).
\]
\item[(iii)] If every variable of $\varphi$ occurs in $\varphi$ both positively and negatively, then $\lambda=2p$, $L\ge2p$ and $s(G)>4p^2-2p^2/k-2p$.
\end{enumerate}
\end{Proposition}
\begin{proof}
(i) By Lemma~\ref{lem:satbound}, $n>q\beta\ge q(2qp^2+1-p)=q^2p^2+q(qp^2+1-p)>q^2p^2$, so $k\ge qp\ge p$. A clause vertex $c_{j,t}$ has degree $|C_j|\le p\le k$. A literal vertex $\ell$ is adjacent to its complement and to the $\beta$ clause vertices of each of the $o_\ell$ clauses that contain it, so it has degree $1+\beta o_\ell$; for $o_\ell=0$ this is $1\le k$. Since $\beta+p>2p\sqrt n\ge2pk$ (Lemma~\ref{lem:satbound}), $\beta>2pk-p\ge k$, so for $o_\ell\ge1$ the degree $1+\beta o_\ell$ exceeds $k$. The formula for $s(G)$ is the definition of the splitting excess. (ii) Since $\beta^*\ge2qp^2+1-p\ge2$, the integer $\beta-1\ge1$ is not a solution of the inequality of Lemma~\ref{lem:satbound}, so $\beta-1+p\le2p\sqrt{2p+q(\beta-1)}<2p\sqrt n<2p(k+1)$, that is $\beta<2pk+p+1$; together with $\beta>2pk-p$ this gives $2p-p/k<\beta/k<2p+(p+1)/k$. For every real $x$, $x-1\le\lceil x\rceil-1<x$, so by (i)
\[
\frac{\beta L+\lambda}{k}-\lambda\ \le\ s(G)\ <\ \frac{\beta L+\lambda}{k}.
\]
The lower bound is larger than $(2p-p/k)L-\lambda$, and the upper bound is smaller than $(2p+(p+1)/k)L+\lambda/k$. Dividing by $2pL$ and using $\lambda\le2p$ and $(p+1)/(2p)\le1$ gives the ratio bounds. (iii) Every variable gives two literals with $o_\ell\ge1$, so $\lambda=2p$ and $L=\sum_\ell o_\ell\ge2p$; since $2p-p/k>0$, (ii) gives $s(G)>(2p-p/k)\cdot2p-2p$.
\end{proof}
By Proposition~\ref{prop:satexcess}(i), $k\ge qp$, so both error terms in (ii) tend to $0$ as $qp$ and $L$ grow, and $s(G)$ is asymptotic to $2pL$.

Let $\mu(\varphi)$ be the least number of clauses of $\varphi$ falsified by an assignment, so that $\mu(\varphi)=0$ if and only if $\varphi$ is satisfiable. For a set $F$ of clause indices, let $U(F)=\bigcup_{j\in F}C_j$ and let $c(F)$ be the number of variables $x_r$ with $x_r\in U(F)$ and $\neg x_r\in U(F)$. A set $T$ of literals \emph{completes} $F$ if, for every variable $x_r$, $T$ contains the complement of $\ell$ when $\ell$ is the only one of $x_r,\neg x_r$ in $U(F)$, exactly one of $x_r,\neg x_r$ when neither lies in $U(F)$, and neither when both lie in $U(F)$, and if $T$ contains a literal of every clause $C_j$ with $j\notin F$. $F$ is \emph{admissible} if some $T$ completes it.
\begin{Theorem}[Independent domination and maximum satisfiability]
\label{thm:maxsat}
Let $\beta\ge1$ and $G=G_\beta(\varphi)$.
\begin{enumerate}
\item[(i)] The independent dominating sets of $G$ are exactly the sets $T\cup\{c_{j,t}:j\in F,\ t\le\beta\}$ with $F$ admissible and $T$ completing $F$, and such a set has $\beta|F|+p-c(F)$ vertices; hence $i(G)=\min_{F\text{ admissible}}\bigl(\beta|F|+p-c(F)\bigr)$.
\item[(ii)] $\beta\,\mu(\varphi)\le i(G)\le\beta\,\mu(\varphi)+p$; if $\beta>p$, then $\mu(\varphi)=\lfloor i(G)/\beta\rfloor$.
\item[(iii)] If $\beta>p$, every independent dominating set $D$ of $G$ contains the clause vertices of exactly $\lfloor|D|/\beta\rfloor$ clauses, and its literal vertices, completed by arbitrary values on the variables with no literal in $D$, form an assignment that falsifies at most $\lfloor|D|/\beta\rfloor$ clauses.
\item[(iv)] If $\beta>p$ and $|D|\le\rho\,i(G)$ for some $\rho\ge1$, that assignment falsifies at most $\rho\,(\mu(\varphi)+p/\beta)$ clauses.
\end{enumerate}
For $\beta=\hat\beta$ and $\beta=\beta^*$, (ii)--(iv) apply, since $\hat\beta\ge p+1$ and $\beta^*\ge2qp^2+1-p>p$ (Lemmas~\ref{lem:sathat} and~\ref{lem:satbound}).
\end{Theorem}
\begin{proof}
(i) Let $D$ be an independent dominating set, $F$ the set of indices of the clauses with a clause vertex in $D$, and $T$ the set of literal vertices of $D$. By Lemma~\ref{lem:satids}(ii), $D$ contains $c_{j,1},\dots,c_{j,\beta}$ for every $j\in F$ and no other clause vertex. Since $D$ is independent, $T$ contains no literal of $U(F)$, which is adjacent to a clause vertex of $D$, and at most one of $x_r,\neg x_r$. A literal vertex $\ell\notin T$ is dominated by its complement or by a clause vertex of $D$, that is, its complement lies in $T$ or $\ell\in U(F)$. If both $x_r,\neg x_r$ lie in $U(F)$, neither lies in $T$. If only $\ell$ lies in $U(F)$, then $\ell\notin T$ and the complement of $\ell$, which is not in $U(F)$, is dominated only if it lies in $T$. If neither lies in $U(F)$, one of them lies in $T$. A clause vertex $c_{j,t}$ with $j\notin F$ is dominated by a literal of $C_j$ in $T$. Hence $T$ completes $F$. Conversely, if $T$ completes $F$, the set $D=T\cup\{c_{j,t}:j\in F,\ t\le\beta\}$ is independent, because clause vertices are pairwise non-adjacent, $T$ holds at most one literal of every variable and no literal of $U(F)$; it dominates every literal vertex not in $T$, by its complement or by a clause vertex of $F$, and every clause vertex $c_{j,t}$ with $j\notin F$, by a literal of $C_j$ in $T$. $T$ contains one literal of each of the $p-c(F)$ variables that do not have both literals in $U(F)$, so $|D|=\beta|F|+p-c(F)$. (ii) Let $\sigma$ be an assignment that falsifies exactly the $\mu(\varphi)$ clauses of a set $F_\sigma$. Every literal of $U(F_\sigma)$ is false under $\sigma$, so no variable has both literals in $U(F_\sigma)$ and $c(F_\sigma)=0$, and the set of true literals of $\sigma$ completes $F_\sigma$; by (i), $i(G)\le\beta\mu(\varphi)+p$. Conversely, let $T$ complete an admissible $F$. $T$ holds at most one literal of every variable, so it extends to an assignment by arbitrary values on the variables with no literal in $T$; this assignment satisfies every clause $C_j$ with $j\notin F$, so $\mu(\varphi)\le|F|$ and $\beta|F|+p-c(F)\ge\beta|F|\ge\beta\mu(\varphi)$, since $c(F)\le p$. If $\beta>p$, then $\beta\mu(\varphi)\le i(G)<\beta(\mu(\varphi)+1)$. (iii) By (i), $|D|=\beta|F|+p-c(F)$ with $0\le p-c(F)\le p<\beta$, so $|F|=\lfloor|D|/\beta\rfloor$, and the assignment satisfies every clause outside $F$, as in (ii). (iv) By (iii) and (ii), the number of falsified clauses is at most $|D|/\beta\le\rho\,i(G)/\beta\le\rho\,(\mu(\varphi)+p/\beta)$.
\end{proof}
Lemma~\ref{lem:satids}(iv) and (v) are the cases $\mu(\varphi)=0$ and $\mu(\varphi)=1$ of Theorem~\ref{thm:maxsat}.

With $\beta=\hat\beta$, \texttt{satypy} builds $G=G_{\beta}(\varphi)$ and runs Algorithm~\ref{alg:main} on it, with output $S$. Without branching (Proposition~\ref{prop:branch}), it answers SATISFIABLE, with the literals of $S$, if $|S|<\beta$ and the assignment passes the check; UNSATISFIABLE if $|S|>2p^2$, that is, if $|S|/p>2p$; and UNKNOWN otherwise. The number of copies $\beta^*$ of Lemma~\ref{lem:satbound}, with the threshold $|S|>2\sqrt n\,p$, is the choice for the ratio $2\sqrt n$.

\begin{Theorem}[Decisions of the MIDS stage]
\label{thm:sat}
Let $\beta=\hat\beta$ and $G=G_\beta(\varphi)$ with $n$ vertices, and let $S$ be the output of Algorithm~\ref{alg:main} on $G$.
\begin{enumerate}
\item[(i)] If $|S|<\beta$, then the literal vertices of $S$ form a satisfying assignment of $\varphi$, and the answer is SATISFIABLE.
\item[(ii)] If $|S|\ge\beta$, then $|S|\ge\beta+p>2p^2$, and the answer is UNSATISFIABLE; the stage never answers UNKNOWN.
\item[(iii)] If $\varphi$ is unsatisfiable, the answer is UNSATISFIABLE.
\item[(iv)] If $\varphi$ is satisfiable, the answer is UNSATISFIABLE if and only if $S$ contains a clause vertex, and then $|S|/i(G)\ge(\beta+p)/p>2p$.
\item[(v)] If $|S|/i(G)\le2p$, the answer is correct.
\end{enumerate}
\end{Theorem}
\begin{proof}
$S$ is an independent dominating set of $G$ (Theorem~\ref{thm:correctness}), and $\beta\ge p+1$ (Lemma~\ref{lem:sathat}). (i) $|S|<\beta<\beta+p$, so $S$ contains no clause vertex by Lemma~\ref{lem:satids}(iii), and Lemma~\ref{lem:satids}(i) gives the assignment. It consists of one literal of every variable of $\varphi$, and the committed literals of the first stage satisfy the clauses that the first stage removed from the input formula and contain no variable of $\varphi$, so their union passes the check. (ii) $|S|\ge\beta>p$, so $|S|\ge\beta+p$ by Lemma~\ref{lem:satids}(iv), and $\beta+p>2p^2$ by Lemma~\ref{lem:sathat}. (iii) $|S|\ge i(G)\ge\beta+p$ by Lemma~\ref{lem:satids}(iv), and (ii) applies. (iv) $i(G)=p$ by Lemma~\ref{lem:satids}(iv); by (i) and (ii) the answer is UNSATISFIABLE if and only if $|S|\ge\beta$, that is, by Lemma~\ref{lem:satids}(i) and (iii), if and only if $S$ contains a clause vertex, and then $|S|\ge\beta+p$. (v) If $\varphi$ is satisfiable, $|S|\le2p\,i(G)=2p^2<\beta+p$, so $S$ contains no clause vertex by Lemma~\ref{lem:satids}(iii), and the answer is SATISFIABLE by (iv) and (i); if $\varphi$ is unsatisfiable, (iii) applies.
\end{proof}

Independently of any conjecture, Theorem~\ref{thm:sat} shows that \texttt{satypy} answers UNSATISFIABLE on every unsatisfiable formula, that every SATISFIABLE answer carries a satisfying assignment, and that a wrong answer can only be UNSATISFIABLE on a satisfiable formula on which Algorithm~\ref{alg:main} has ratio larger than $2p=2i(G)$.

\paragraph{The proved bound of the degree-splitting strategy} Theorem~\ref{thm:split} cannot replace the ratio assumption of Theorem~\ref{thm:sat}(v), for any number of copies.
\begin{Proposition}[No separation by the splitting bound]
\label{prop:nosep}
For every $\beta\ge1$ and every satisfiable $\varphi$, the graph $G=G_\beta(\varphi)$ satisfies $\lfloor\sqrt n\rfloor\,(i(G)+s(G))\ge p+q\beta\ge\beta+p$. Hence the bound of Theorem~\ref{thm:split} on a satisfiable formula is never smaller than the size $\beta+p$ that Lemma~\ref{lem:satids}(iii) guarantees for every independent dominating set with a clause vertex, and it does not imply that the output contains no clause vertex; in particular this holds for $\beta=\hat\beta$, for $\beta=\beta^*$ and for $\beta=\beta_t$ of Theorem~\ref{thm:satgap}.
\end{Proposition}
\begin{proof}
$i(G)=p$ by Lemma~\ref{lem:satids}(iv), and $n=2p+q\beta$, so Proposition~\ref{prop:splitlower} gives $\lfloor\sqrt n\rfloor\,(p+s(G))\ge n-p=p+q\beta\ge p+\beta$.
\end{proof}

\paragraph{SAT-IDS graphs for the ratio $n^{1-1/t}$} The number of copies can be chosen for any ratio of the form $n^{1-\varepsilon}$ with $\varepsilon=1/t$.
\begin{Theorem}[Gap of the SAT-IDS graph for the ratio $n^{1-1/t}$]
\label{thm:satgap}
For an integer $t\ge2$, let $\beta_t=p^t(3q)^{t-1}+1$ and $G=G_{\beta_t}(\varphi)$, with $n=2p+q\beta_t=3^{t-1}p^tq^t+q+2p$ vertices.
\begin{enumerate}
\item[(i)] $\beta_t+p>p\,n^{1-1/t}$; hence $i(G)=p$ if $\varphi$ is satisfiable, and $i(G)\ge\beta_t+p>p\,n^{1-1/t}$ otherwise.
\item[(ii)] For every independent dominating set $D$ of $G$ with $|D|\le n^{1-1/t}\,i(G)$: $\varphi$ is satisfiable if and only if $|D|<\beta_t$, and then the literal vertices of $D$ form a satisfying assignment.
\item[(iii)] $G$ has $p+\beta_t\sum_j|C_j|$ edges and is built in time polynomial in $p$ and $q$ for every fixed $t$.
\end{enumerate}
\end{Theorem}
\begin{proof}
(i) $\beta_t>p$, so $2p+q\beta_t<3q\beta_t$. Since $\beta_t>p^t(3q)^{t-1}$, $\beta_t^{1/t}>p\,(3q)^{(t-1)/t}$, and $\beta_t=\beta_t^{1/t}\beta_t^{(t-1)/t}>p\,(3q\beta_t)^{1-1/t}>p\,n^{1-1/t}$, so $\beta_t+p>p\,n^{1-1/t}$. Lemma~\ref{lem:satids}(iv) applies because $\beta_t\ge p$. (ii) If $\varphi$ is satisfiable, $|D|\le n^{1-1/t}p<\beta_t+p$, so $D$ contains no clause vertex by Lemma~\ref{lem:satids}(iii), and Lemma~\ref{lem:satids}(i) gives $|D|=p<\beta_t$ and the assignment. If $\varphi$ is unsatisfiable, $|D|\ge i(G)\ge\beta_t+p$. (iii) Definition~\ref{def:satids}; $n$ and the number of edges are polynomials in $p$ and $q$ of degree $2t$ and $2t+1$.
\end{proof}
\begin{Corollary}[Two values of the ratio]
\label{cor:dichotomy}
Let $\varphi$ be satisfiable, $\beta\ge p$, $G=G_\beta(\varphi)$ with $n$ vertices, and $D$ an independent dominating set of $G$. Then either $|D|/i(G)=1$, and the literal vertices of $D$ form a satisfying assignment, or $D$ contains a clause vertex and $|D|/i(G)\ge(\beta+p)/p$. For $\beta=\hat\beta$, $(\beta+p)/p>2p$; for $\beta=\beta^*$, $(\beta+p)/p>2\sqrt n$; for $\beta=\beta_t$ with $t\ge2$, $(\beta+p)/p>n^{1-1/t}$, in particular $(\beta_4+p)/p>n^{3/4}$. Hence, for $\beta=\hat\beta$ and every $\rho\le2p$, for $\beta=\beta^*$ and every $\rho\le2\sqrt n$, and for $\beta=\beta_t$ and every $\rho\le n^{1-1/t}$, $|D|/i(G)\le\rho$ holds if and only if $D$ is a minimum independent dominating set of $G$.
\end{Corollary}
\begin{proof}
$i(G)=p$ by Lemma~\ref{lem:satids}(iv). If $D$ contains no clause vertex, $|D|=p$ and its literal vertices form a satisfying assignment by Lemma~\ref{lem:satids}(i); otherwise $|D|\ge\beta+p$ by Lemma~\ref{lem:satids}(iii). The inequalities for $\hat\beta$, $\beta^*$ and $\beta_t$ are Lemmas~\ref{lem:sathat} and~\ref{lem:satbound} and Theorem~\ref{thm:satgap}(i), divided by $p$; in both cases the second alternative gives $|D|/i(G)>\rho$, and the first gives $|D|=i(G)$.
\end{proof}


\begin{Corollary}[Inapproximability through the SAT-IDS graph]
\label{cor:inapprox}
For every $\varepsilon>0$, unless $\mathrm{P}=\mathrm{NP}$, no polynomial-time algorithm returns, on every graph with $n$ vertices, an independent dominating set of size at most $n^{1-\varepsilon}\,i(G)$.
\end{Corollary}
\begin{proof}
Let $t\ge\max(2,1/\varepsilon)$, so that $n^{1-\varepsilon}\le n^{1-1/t}$. Given a formula in conjunctive normal form, unit propagation and pure literal elimination either decide it or leave a residual formula $\varphi$, every clause a nonempty set of literals with no complementary pair; the graph $G_{\beta_t}(\varphi)$ is built in polynomial time by Theorem~\ref{thm:satgap}(iii), and by Theorem~\ref{thm:satgap}(ii) the size of the returned set decides $\varphi$. Satisfiability of formulas in conjunctive normal form is NP-complete.
\end{proof}
Corollary~\ref{cor:inapprox} is the theorem of Halld{\'o}rsson~\cite{halldorsson1993approximating}; Theorem~\ref{thm:satgap} gives a self-contained proof of it through the SAT-IDS graph.

\begin{Corollary}[Conditional consequence for SAT]
\label{cor:sat}
If Conjecture~\ref{conj:sqrt} is proved, then the MIDS stage of \texttt{satypy} with $\beta=\beta_4=27p^4q^3+1$ in place of $\hat\beta$, answering SATISFIABLE if and only if $|S|<\beta_4$, decides every formula in conjunctive normal form correctly in polynomial time.
\end{Corollary}
\begin{proof}
Unit propagation, pure literal elimination and the implication-graph solver are exact and run in polynomial time. $G_{\beta_4}(\varphi)$ has $n=27p^4q^4+q+2p$ vertices and is built in polynomial time (Theorem~\ref{thm:satgap}(iii)), and Algorithm~\ref{alg:main} runs on it in polynomial time (Theorem~\ref{thm:runtime}). Conjecture~\ref{conj:sqrt} gives $|S|\le n^{3/4}\,i(G)$, and Theorem~\ref{thm:satgap}(ii) with $t=4$ gives the correctness.
\end{proof}
Corollary~\ref{cor:sat} is a second route to the conclusion $\mathrm{P}=\mathrm{NP}$ of Theorem~\ref{thm:sqrtpnp}.

\paragraph{Branching on the clause named by the output} When $|S|\ge\beta$, the output itself names a clause on which the formula can be split exactly. \texttt{satypy} decodes the literal vertices of $S$, completes them with the value false on the variables with no literal in $S$, and, if the resulting assignment satisfies $\varphi$, answers SATISFIABLE with it; otherwise it chooses a shortest falsified clause $C$ and decides every formula $\varphi\wedge\ell$, $\ell\in C$, by the same procedure with the depth decreased by one, up to a fixed depth $d$ ($d=2$ by default). It answers SATISFIABLE if a branch is satisfiable, with the checked assignment of that branch, and UNSATISFIABLE if every branch is unsatisfiable; at depth $0$ it uses the rule of Theorem~\ref{thm:sat}.
\begin{Proposition}[Branching]
\label{prop:branch}
Let $\beta>p$, $G=G_\beta(\varphi)$, $S$ an independent dominating set of $G$ with $|S|\ge\beta$, and $w$ the largest clause width.
\begin{enumerate}
\item[(i)] $S$ contains the clause vertices of exactly $\lfloor|S|/\beta\rfloor\ge1$ clauses, and the decoded assignment falsifies at most $\lfloor|S|/\beta\rfloor$ clauses; if it falsifies none, $\varphi$ is satisfiable.
\item[(ii)] For every clause $C$ of $\varphi$, $\varphi$ is satisfiable if and only if $\varphi\wedge\ell$ is satisfiable for some literal $\ell\in C$.
\item[(iii)] Branching to depth $d$ runs Algorithm~\ref{alg:main} at most $\sum_{h=0}^{d}w^h$ times, each time on the SAT-IDS graph of a formula with at most $p$ variables and $q$ clauses, so it runs in polynomial time for every fixed $d$.
\item[(iv)] Every UNSATISFIABLE answer on an unsatisfiable formula and every SATISFIABLE answer is correct. If a satisfiable $\varphi$ is answered UNSATISFIABLE, there are satisfiable formulas $\varphi=\varphi_0,\varphi_1,\dots,\varphi_d$, each $\varphi_{h+1}$ the residual formula of $\varphi_h\wedge\ell_h$ for a literal $\ell_h$, such that the output of Algorithm~\ref{alg:main} on the SAT-IDS graph of every $\varphi_h$ contains a clause vertex.
\end{enumerate}
\end{Proposition}
\begin{proof}
(i) Theorem~\ref{thm:maxsat}(iii); $\lfloor|S|/\beta\rfloor\ge1$ since $|S|\ge\beta$. (ii) Every satisfying assignment of $\varphi$ satisfies $C$, hence some $\ell\in C$, and satisfies $\varphi\wedge\ell$; the converse is immediate. (iii) Every node of the branching tree runs Algorithm~\ref{alg:main} once and has at most $w$ children, and the tree has depth at most $d$. Fixing a literal and simplifying removes at least one variable and no clause is added, so every formula of the tree has at most $p$ variables and $q$ clauses, and its SAT-IDS graph has polynomial size by Lemma~\ref{lem:sathat}. (iv) SATISFIABLE answers carry checked assignments. An unsatisfiable formula is answered UNSATISFIABLE at every node: by (ii) every branch is unsatisfiable, and at depth $0$ by Theorem~\ref{thm:sat}(iii). Let $\varphi_0$ be satisfiable and answered UNSATISFIABLE. The exact stages answer it correctly, so it reaches the MIDS stage and the output on its graph has $|S|\ge\beta$, hence contains a clause vertex (Lemma~\ref{lem:satids}(i) and (iii)). If $d\ge1$, by (ii) some branch $\varphi_0\wedge\ell_0$ is satisfiable, and since every branch is answered UNSATISFIABLE, so is this one; its residual formula $\varphi_1$ is satisfiable and answered UNSATISFIABLE with depth $d-1$, and induction on $d$ gives the chain.
\end{proof}

\section{Experiments}
\label{sec:experiments}
All experiments use \textsc{Siriaisa} 0.0.8 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. Section~\ref{sec:satexp} uses the scripts \texttt{small\_formulas.py} and \texttt{strategy\_search.py} of the folder \texttt{car/} of the \texttt{satypy} repository~\cite{Vega26Satypy}, which imports that repository's own \texttt{satypy/}. 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; $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.
\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 $36.6$\,ms per instance on average, and the integer program $9.5$\,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{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 $15$ of them $|S|$ equals the best solution found by the integer program, 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 $10.8$\,s per instance and $362.2$\,s in total; the integer programs took $1\,439.5$\,s and the whole run $1\,803.9$\,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 & 23.4 \\
3D grid & 2 & 1 & 1 & 0 & 1 & 1.0750 & 1.0375 & 5.7 \\
complete bipartite & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 2.9 \\
crown graph & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 0.1 \\
double cover $G\times K_2$ of random regular & 12 & 8 & 8 & 0 & 4 & 1.1765 & 1.0370 & 52.6 \\
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 & 49.1 \\
hypercube & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 3.3 \\
hypercube, 50\% edges kept & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 6.8 \\
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.6 \\
random bipartite (1:2) & 18 & 15 & 15 & 0 & 3 & 1.4545 & 1.0657 & 50.3 \\
random bipartite (balanced) & 18 & 15 & 15 & 0 & 3 & 1.4167 & 1.0602 & 53.0 \\
random $d$-regular bipartite & 18 & 12 & 12 & 0 & 6 & 1.2917 & 1.0623 & 63.7 \\
random tree & 6 & 6 & 6 & 0 & 0 & 1.0000 & 1.0000 & 20.8 \\
\midrule
\textbf{All} & \textbf{112} & \textbf{95} & \textbf{95} & \textbf{0} & \textbf{17} & \textbf{1.4545} & \textbf{1.0349} & \textbf{362.2} \\
\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\,061.5$\,s; \textsc{Siriaisa} took at most $25.6$\,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 $K_{200,200}$, whose integer program reached its time limit and for which $i=200$ by Proposition~\ref{prop:complete}; 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\,286.8$\,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 & 19.1 \\
planar (Delaunay) & 4 & 100--400 & 12 & 4 & 0 & 0.000 & 4 & 4 & 3 & 1 & 0 & 1.0161 & 18.6 \\
random 4-regular & 4 & 100--400 & 4 & 4 & 0 & 0.000 & 4 & 2 & 2 & 0 & 2 & 1.1481 & 20.6 \\
random 5-regular & 4 & 100--400 & 5 & 4 & 0 & 0.000 & 4 & 2 & 2 & 0 & 2 & 1.2239 & 18.5 \\
random 6-regular & 4 & 100--400 & 6 & 4 & 0 & 0.000 & 4 & 2 & 2 & 0 & 2 & 1.2586 & 17.8 \\
random 4-regular bipartite$^{*}$ & 4 & 100--400 & 4 & 4 & 0 & 0.000 & 4 & 2 & 2 & 0 & 2 & 1.1481 & 19.8 \\
random 5-regular bipartite$^{*}$ & 4 & 100--400 & 5 & 4 & 0 & 0.000 & 4 & 2 & 2 & 0 & 2 & 1.2059 & 17.8 \\
SC-IDS, $B=4$ & 4 & 94--375 & 4 & 4 & 0 & 0.000 & 4 & 4 & 3 & 1 & 0 & 1.0080 & 21.9 \\
SC-IDS, $B=6$ & 4 & 93--384 & 6 & 4 & 0 & 0.000 & 4 & 4 & 4 & 0 & 0 & 1.0000 & 19.3 \\
VC-IDS, $3$-regular $H$ & 4 & 240--1\,000 & 3 & 4 & 0 & 0.000 & 4 & 2 & 2 & 0 & 2 & 1.4400 & 34.6 \\
$G(n,1/2)$ & 4 & 100--400 & 230 & 0 & 3\,783 & 0.473 & 0 & 2 & 2 & 0 & 2 & 2.5000 & 10.0 \\
complete $K_n$ & 4 & 100--400 & 399 & 0 & 7\,600 & 0.950 & 0 & 4 & 4 & 0 & 0 & 1.0000 & 2.1 \\
$K_{n/2,n/2}$ & 4 & 100--400 & 200 & 0 & 3\,600 & 0.450 & 4 & 4 & 4 & 0 & 0 & 1.0000 & 9.5 \\
$K_{n/4,3n/4}$ & 4 & 100--400 & 300 & 0 & 2\,600 & 0.325 & 2 & 4 & 4 & 0 & 0 & 1.0000 & 9.4 \\
complete $4$-partite, equal parts & 4 & 100--400 & 300 & 0 & 5\,600 & 0.700 & 0 & 4 & 4 & 0 & 0 & 1.0000 & 10.7 \\
complete $5$-partite, random parts & 4 & 100--400 & 392 & 0 & 5\,889 & 0.736 & 0 & 4 & 4 & 0 & 0 & 1.0000 & 7.5 \\
crown & 4 & 100--400 & 199 & 0 & 3\,600 & 0.450 & 0 & 4 & 4 & 0 & 0 & 1.0000 & 1.1 \\
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 & 11.8 \\
split graph & 4 & 100--400 & 232 & 0 & 209 & 0.055 & 0 & 4 & 4 & 0 & 0 & 1.0000 & 4.5 \\
$G(n,3/n)$ & 4 & 100--400 & 11 & 4 & 0 & 0.000 & 4 & 4 & 3 & 1 & 0 & 1.0075 & 29.4 \\
Barab\'asi--Albert, $m=3$ & 4 & 100--400 & 67 & 0 & 19 & 0.013 & 0 & 4 & 2 & 2 & 0 & 1.0532 & 17.8 \\
power-law bipartite & 4 & 100--400 & 55 & 0 & 6 & 0.004 & 1 & 4 & 4 & 0 & 0 & 1.0000 & 23.6 \\
2D grid & 4 & 100--400 & 4 & 4 & 0 & 0.000 & 4 & 2 & 2 & 0 & 2 & 1.0814 & 24.9 \\
hypercube & 2 & 128--512 & 9 & 2 & 0 & 0.000 & 2 & 1 & 1 & 0 & 1 & 1.2308 & 5.1 \\
Khot--Regev YES & 2 & 640 & 64 & 0 & 323 & 0.020 & 0 & 0 & 0 & 0 & 2 & 15.9000 & 7.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 & 19.2 \\
VC-IDS, Khot--Regev $H$ & 2 & 49\,096--51\,550 & 64 & 2 & 0 & 0.000 & 2 & 0 & 0 & 0 & 2 & 22.1825 & 64.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{465.9} \\
\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 $582.7$\,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 & 1.4 \\
random cubic & 4 & 100--400 & 0 & 4 & 2 & 2 & 0 & 2 & 1.0693 & 0.2700 & 24.1 \\
random cubic bipartite & 4 & 100--400 & 0 & 4 & 2 & 2 & 0 & 2 & 1.0693 & 0.2700 & 25.5 \\
double cover of random cubic & 4 & 100--400 & 0 & 4 & 2 & 2 & 0 & 2 & 1.0693 & 0.2800 & 24.1 \\
cubic planar (dual of Delaunay) & 4 & 100--400 & 0 & 4 & 2 & 2 & 0 & 2 & 1.0792 & 0.2725 & 22.3 \\
cubic planar bipartite & 4 & 100--400 & 0 & 4 & 2 & 2 & 0 & 2 & 1.0693 & 0.2800 & 25.0 \\
random cubic, $20\%$ edges deleted & 4 & 100--400 & 0 & 4 & 4 & 4 & 0 & 0 & 1.0000 & 0.3250 & 33.5 \\
prism $C_t\times K_2$ & 4 & 100--402 & 0 & 4 & 3 & 3 & 0 & 1 & 1.0099 & 0.2600 & 15.1 \\
M\"obius ladder & 2 & 100--400 & 0 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 0.2525 & 12.4 \\
generalized Petersen $GP(t,2)$ & 2 & 100--400 & 0 & 2 & 1 & 1 & 0 & 1 & 1.1650 & 0.3000 & 13.0 \\
generalized Petersen $GP(t,3)$ & 2 & 100--400 & 0 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 0.2600 & 5.9 \\
\midrule
\textbf{All} & \textbf{61} & & & \textbf{46} & \textbf{49} & \textbf{49} & \textbf{0} & \textbf{12} & \textbf{1.1650} & \textbf{0.5000} & \textbf{202.4} \\
\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 $2.0$\,ms per instance and building the graph at most $53$\,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.2143$. The run took $241.0$\,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.2143 & 5.1 \\
short chords, degree $\approx3$ & 4 & 100--400 & 904 & 14 & 3 & 2 & 0.002 & 3 & 4 & 4 & 0 & 0 & 1.0000 & 14.7 \\
short chords, degree $\approx10$ & 4 & 100--400 & 2\,500 & 29 & 0 & 107 & 0.119 & 0 & 4 & 2 & 2 & 0 & 1.0405 & 8.8 \\
short chords, degree $\approx\sqrt n$ & 4 & 100--400 & 5\,488 & 57 & 0 & 354 & 0.092 & 0 & 4 & 2 & 2 & 0 & 1.0600 & 6.1 \\
permutation graph & 4 & 100--400 & 41\,274 & 393 & 0 & 3\,925 & 0.563 & 0 & 4 & 4 & 0 & 0 & 1.0000 & 7.4 \\
$2$ hub chords & 4 & 100--400 & 532 & 102 & 0 & 15 & 0.007 & 1 & 4 & 4 & 0 & 0 & 1.0000 & 11.9 \\
$4$ hub chords & 4 & 100--400 & 599 & 54 & 0 & 14 & 0.006 & 1 & 4 & 4 & 0 & 0 & 1.0000 & 13.0 \\
diameters ($K_n$) & 2 & 100--400 & 79\,800 & 399 & 0 & 7\,600 & 1.000 & 0 & 2 & 2 & 0 & 0 & 1.0000 & 0.7 \\
$K_{n/2,n/2}$ & 2 & 100--400 & 40\,000 & 200 & 0 & 3\,600 & 0.474 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 3.4 \\
$K_{n/4,3n/4}$ & 2 & 100--400 & 30\,000 & 300 & 0 & 2\,600 & 0.361 & 1 & 2 & 2 & 0 & 0 & 1.0000 & 3.2 \\
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.2143} & \textbf{74.4} \\
\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 $25$ 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 $1$ and $2$ vertices on two 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$, and on the open Khot--Regev graph it has $173$ vertices against $170$ and $L=158$. The largest time of \textsc{Siriaisa} on an instance is $13.2$\,s, and the run took $1\,551.2$\,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 & 11.2 \\
random $B$-regular bipartite (double cover) & 4 & 2 & 256 & 512 & 2 & 0 & 0 & 0 & 2 & 1.1154 & 1.1058 & 12.1 \\
$B$-regular, planted perfect code & 4 & 2 & 260 & 520 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 0.9 \\
SC-IDS & 4 & 2 & 323 & 430 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 13.7 \\
VC-IDS, $B$-regular $H$ & 4 & 2 & 260 & 320 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 15.0 \\
random $B$-regular & 8 & 2 & 256 & 1\,024 & 2 & 0 & 0 & 0 & 2 & 1.3793 & 1.3621 & 5.1 \\
random $B$-regular bipartite (double cover) & 8 & 2 & 256 & 1\,024 & 2 & 0 & 0 & 0 & 2 & 1.3448 & 1.3448 & 5.3 \\
$B$-regular, planted perfect code & 8 & 2 & 261 & 1\,044 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 0.5 \\
SC-IDS & 8 & 2 & 331--334 & 769 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 10.7 \\
VC-IDS, $B$-regular $H$ & 8 & 2 & 250 & 320 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 15.5 \\
random $B$-regular & 16 & 2 & 256 & 2\,048 & 2 & 0 & 0 & 0 & 2 & 1.5625 & 1.5312 & 3.3 \\
random $B$-regular bipartite (double cover) & 16 & 2 & 256 & 2\,048 & 2 & 0 & 0 & 0 & 2 & 1.5625 & 1.5625 & 4.4 \\
$B$-regular, planted perfect code & 16 & 2 & 272 & 2\,176 & 2 & 2 & 2 & 0 & 0 & 1.0000 & 1.0000 & 0.6 \\
SC-IDS & 16 & 2 & 318--321 & 1\,353 & 2 & 2 & 0 & 2 & 0 & 1.0115 & 1.0114 & 9.7 \\
VC-IDS, $B$-regular $H$ & 16 & 2 & 882 & 1\,152 & 2 & 2 & 1 & 1 & 0 & 1.0033 & 1.0016 & 20.4 \\
random $B$-regular & 32 & 2 & 1\,024 & 16\,384 & 2 & 0 & 0 & 0 & 2 & 2.2188 & 2.2188 & 6.0 \\
random $B$-regular bipartite (double cover) & 32 & 2 & 1\,024 & 16\,384 & 2 & 0 & 0 & 0 & 2 & 2.2500 & 2.2500 & 4.3 \\
$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 & 6.8 \\
VC-IDS, $B$-regular $H$ & 32 & 2 & 3\,298 & 4\,352 & 2 & 2 & 0 & 2 & 0 & 1.0009 & 1.0009 & 13.6 \\
Khot--Regev YES, $d=3$, $s_b=4$ & 12 & 2 & 160 & 382 & 2 & 2 & 1 & 1 & 0 & 1.0364 & 1.0182 & 12.3 \\
Khot--Regev YES, $d=3$, $s_b=8$ & 24 & 2 & 608 & 2\,938 & 2 & 1 & 0 & 1 & 1 & 1.0949 & 1.0505 & 12.4 \\
\midrule
\textbf{All} & & \textbf{44} & & & \textbf{44} & \textbf{25} & \textbf{18} & \textbf{7} & \textbf{19} & \textbf{2.2500} & \textbf{1.2112} & \textbf{185.3} \\
\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.016$\,s (\texttt{MANN\_a9}) to $15.0$\,s (\texttt{p\_hat700-1}), with mean $2.87$\,s and total $195.1$\,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.13 & \texttt{brock200\_2} & 4 & 1.40 \\
\texttt{brock200\_3} & 5 & 1.16 & \texttt{brock200\_4} & 6 & 1.16 \\
\texttt{brock400\_1} & 10 & 1.66 & \texttt{brock400\_2} & 11 & 1.54 \\
\texttt{brock400\_3} & 11 & 1.53 & \texttt{brock400\_4} & 11 & 1.58 \\
\texttt{brock800\_1} & 8 & 6.97 & \texttt{brock800\_2} & 9 & 6.72 \\
\texttt{brock800\_3} & 9 & 6.99 & \texttt{brock800\_4} & 9 & 6.68 \\
\texttt{c-fat200-1} & 10 & 1.21 & \texttt{c-fat200-2} & 22 & 1.21 \\
\texttt{c-fat200-5} & 56 & 1.43 & \texttt{c-fat500-1} & 12 & 6.10 \\
\texttt{c-fat500-10} & 124 & 4.06 & \texttt{c-fat500-2} & 24 & 6.25 \\
\texttt{c-fat500-5} & 62 & 4.94 & \texttt{C1000.9} & 31 & 3.43 \\
\texttt{C125.9} & 14 & 2.02 & \texttt{C250.9} & 18 & 1.34 \\
\texttt{C500.9} & 25 & 1.58 & \texttt{gen200\_p0.9\_44} & 16 & 1.45 \\
\texttt{gen200\_p0.9\_55} & 16 & 1.54 & \texttt{gen400\_p0.9\_55} & 21 & 1.41 \\
\texttt{gen400\_p0.9\_65} & 22 & 1.41 & \texttt{gen400\_p0.9\_75} & 24 & 1.36 \\
\texttt{hamming10-2} & 128 & 2.90 & \texttt{hamming10-4} & 13 & 5.25 \\
\texttt{hamming6-2} & 12 & 0.91 & \texttt{hamming6-4} & 2 & 0.04 \\
\texttt{hamming8-2} & 32 & 2.72 & \texttt{hamming8-4} & 4 & 1.83 \\
\texttt{johnson16-2-4} & 8 & 1.34 & \texttt{johnson32-2-4} & 16 & 1.61 \\
\texttt{johnson8-2-4} & 4 & 0.36 & \texttt{johnson8-4-4} & 7 & 1.96 \\
\texttt{keller4} & 5 & 1.40 & \texttt{keller5} & 10 & 4.31 \\
\texttt{MANN\_a27} & 27 & 0.13 & \texttt{MANN\_a45} & 45 & 0.19 \\
\texttt{MANN\_a81} & 81 & 0.34 & \texttt{MANN\_a9} & 9 & 0.02 \\
\texttt{p\_hat1000-3} & 15 & 7.88 & \texttt{p\_hat300-1} & 3 & 2.18 \\
\texttt{p\_hat300-2} & 5 & 1.73 & \texttt{p\_hat300-3} & 10 & 1.20 \\
\texttt{p\_hat500-1} & 3 & 5.24 & \texttt{p\_hat500-2} & 7 & 7.33 \\
\texttt{p\_hat500-3} & 11 & 4.20 & \texttt{p\_hat700-1} & 3 & 15.02 \\
\texttt{p\_hat700-2} & 7 & 10.86 & \texttt{p\_hat700-3} & 14 & 6.19 \\
\texttt{san200\_0.7\_1} & 7 & 1.99 & \texttt{san200\_0.7\_2} & 6 & 1.84 \\
\texttt{san200\_0.9\_1} & 16 & 2.24 & \texttt{san200\_0.9\_2} & 16 & 2.28 \\
\texttt{san200\_0.9\_3} & 15 & 2.39 & \texttt{san400\_0.5\_1} & 4 & 3.81 \\
\texttt{san400\_0.7\_1} & 8 & 1.93 & \texttt{san400\_0.7\_2} & 8 & 1.88 \\
\texttt{san400\_0.7\_3} & 8 & 1.91 & \texttt{san400\_0.9\_1} & 22 & 1.36 \\
\texttt{sanr200\_0.7} & 7 & 1.09 & \texttt{sanr200\_0.9} & 16 & 1.45 \\
\texttt{sanr400\_0.5} & 5 & 2.62 & \texttt{sanr400\_0.7} & 9 & 1.89 \\
\bottomrule
\end{tabular}
\end{table}

\subsection{The SAT-IDS graphs of satypy}
\label{sec:satexp}
The scripts \texttt{small\_formulas.py} and \texttt{strategy\_search.py} decide formulas with \texttt{satypy} 0.0.4, with $\beta=\hat\beta$ copies (Lemma~\ref{lem:sathat}) and branching to depth $2$ (Proposition~\ref{prop:branch}), and with exhaustive search over all assignments, and compare the answers.

\paragraph{Small formulas} The script \texttt{small\_formulas.py} used the eight DIMACS files of the folders \texttt{benchmarks/simple} and \texttt{benchmarks/test\_formulas} of the \texttt{satypy} repository with at most ten variables and $180$ random $3$-CNF formulas, five for every number of variables from $3$ to $5$ and every number of clauses from $1$ to $12$ (seed $2026$). All $188$ answers agree with exhaustive search: $70$ formulas are decided by unit propagation and pure literal elimination, $115$ satisfiable formulas on the SAT-IDS graph of their residual formula, with $|S|=p$, and $3$ unsatisfiable formulas by branching. The SAT-IDS graphs have $38$ to $1\,084$ vertices and $99$ to $3\,222$ edges, and each formula takes at most $5.0$ seconds. Table~\ref{tab:satexp} lists the graphs by residual size $(p,q)$. On the $3$ unsatisfiable formulas $|S|=\beta+p$, so by Theorem~\ref{thm:maxsat}(iii) the output contains the clause vertices of exactly one clause, and $\mu(\varphi)=1$.

\begin{table}[H]
\centering
\scriptsize
\caption{The SAT-IDS graphs of the $118$ formulas of \texttt{small\_formulas.py} decided on the MIDS graph, grouped by the residual size $(p,q)$ and the answer of exhaustive search. ``Count'' is the number of formulas, $\beta=\hat\beta$, $|S|$ the size of the output of Algorithm~\ref{alg:main} on the graph of the residual formula, the same for all formulas of a row, and $2p^2$ the threshold of the rule of Theorem~\ref{thm:sat}.}
\label{tab:satexp}
\begin{tabular}{rrlrrrrrr}
\toprule
$p$ & $q$ & Answer & Count & $\beta$ & $n$ & $|E|$ & $|S|$ & $2p^2$ \\
\midrule
3 & 2 & SAT & 5 & 16 & 38 & 99 & 3 & 18 \\
3 & 3 & SAT & 5 & 16 & 54 & 147 & 3 & 18 \\
3 & 4 & SAT & 8 & 16 & 70 & 195 & 3 & 18 \\
3 & 5 & SAT & 6 & 16 & 86 & 243 & 3 & 18 \\
3 & 6 & SAT & 5 & 16 & 102 & 291 & 3 & 18 \\
3 & 7 & SAT & 6 & 16 & 118 & 339 & 3 & 18 \\
3 & 8 & SAT & 5 & 16 & 134 & 387 & 3 & 18 \\
3 & 8 & UNSAT & 1 & 16 & 134 & 387 & 19 & 18 \\
3 & 9 & SAT & 5 & 16 & 150 & 435 & 3 & 18 \\
3 & 10 & SAT & 4 & 16 & 166 & 483 & 3 & 18 \\
3 & 10 & UNSAT & 1 & 16 & 166 & 483 & 19 & 18 \\
3 & 11 & SAT & 5 & 16 & 182 & 531 & 3 & 18 \\
3 & 12 & SAT & 4 & 16 & 198 & 579 & 3 & 18 \\
3 & 12 & UNSAT & 1 & 16 & 198 & 579 & 19 & 18 \\
4 & 4 & SAT & 4 & 29 & 124 & 352 & 4 & 32 \\
4 & 5 & SAT & 2 & 29 & 153 & 439 & 4 & 32 \\
4 & 6 & SAT & 5 & 29 & 182 & 526 & 4 & 32 \\
4 & 7 & SAT & 4 & 29 & 211 & 613 & 4 & 32 \\
4 & 8 & SAT & 3 & 29 & 240 & 700 & 4 & 32 \\
4 & 9 & SAT & 5 & 29 & 269 & 787 & 4 & 32 \\
4 & 10 & SAT & 5 & 29 & 298 & 874 & 4 & 32 \\
4 & 11 & SAT & 5 & 29 & 327 & 961 & 4 & 32 \\
4 & 12 & SAT & 5 & 29 & 356 & 1\,048 & 4 & 32 \\
5 & 7 & SAT & 2 & 46 & 332 & 971 & 5 & 50 \\
5 & 8 & SAT & 1 & 46 & 378 & 1\,109 & 5 & 50 \\
5 & 9 & SAT & 5 & 46 & 424 & 1\,247 & 5 & 50 \\
5 & 10 & SAT & 2 & 46 & 470 & 1\,385 & 5 & 50 \\
5 & 11 & SAT & 4 & 46 & 516 & 1\,523 & 5 & 50 \\
5 & 12 & SAT & 4 & 46 & 562 & 1\,661 & 5 & 50 \\
6 & 16 & SAT & 1 & 67 & 1\,084 & 3\,222 & 6 & 72 \\
\bottomrule
\end{tabular}
\end{table}

\paragraph{Formulas built for the MIDS stage} The script \texttt{strategy\_search.py} generates $3$-CNF formulas with $3$ to $6$ variables and at most $16$ clauses (seed $2026$) of three kinds and keeps those whose residual formula reaches the SAT-IDS graph: satisfiable formulas with a single satisfying assignment, planted and completed by clauses it satisfies; satisfiable formulas satisfied by neither constant assignment; and unsatisfiable formulas. It obtained $20$, $20$ and $19$ such formulas. For every formula it records the answer of \texttt{satypy} and, on the SAT-IDS graph of the residual formula, the output of every strategy $c_1,\dots,c_{18}$ of Algorithm~\ref{alg:main}. All $59$ answers agree with exhaustive search. On all $40$ satisfiable formulas the output has $|S|=p$ and the answer is decided on the graph without branching; the $19$ unsatisfiable formulas are decided by branching, each with $|S|=\beta+p$ and $\mu(\varphi)=1$. On all $59$ formulas $\lfloor|S|/\beta\rfloor\ge\mu(\varphi)$, and the decoded assignment falsifies at most $\lfloor|S|/\beta\rfloor$ clauses, as Theorem~\ref{thm:maxsat}(ii) and (iii) state. The graphs have $166$ to $1\,084$ vertices and $483$ to $3\,222$ edges, and each formula takes at most $30.7$ seconds. Table~\ref{tab:satstrategies} gives, for every strategy, the number of satisfiable formulas on which it returns $p$ vertices.

\begin{table}[H]
\centering
\small
\caption{Number of the $40$ satisfiable formulas of \texttt{strategy\_search.py} on whose SAT-IDS graph each strategy of Algorithm~\ref{alg:main} returns a minimum independent dominating set ($p$ vertices).}
\label{tab:satstrategies}
\begin{tabular}{lrrrrrrrrr}
\toprule
Strategy & $c_1$ & $c_2$ & $c_3$ & $c_4$ & $c_5$ & $c_6$ & $c_7$ & $c_8$ & $c_9$ \\
Optimal & 14 & 13 & 26 & 9 & 32 & 17 & 0 & 0 & 14 \\
\midrule
Strategy & $c_{10}$ & $c_{11}$ & $c_{12}$ & $c_{13}$ & $c_{14}$ & $c_{15}$ & $c_{16}$ & $c_{17}$ & $c_{18}$ \\
Optimal & 36 & 36 & 0 & 11 & 0 & 39 & 39 & 39 & 40 \\
\bottomrule
\end{tabular}
\end{table}

By Lemma~\ref{lem:sathat}, the SAT-IDS graph with $\hat\beta=2p^2-p+1$ copies grows as $2qp^2$. Table~\ref{tab:satsizes} gives its size for residual $3$-CNF formulas with the numbers of variables and clauses of the uniform random benchmark \texttt{uf20-91} and of three instances of the \texttt{aim} family.

\begin{table}[H]
\centering
\small
\caption{Size of the SAT-IDS graph of a residual $3$-CNF formula with $p$ variables and $q$ clauses and $\hat\beta$ copies (Lemma~\ref{lem:sathat}); $|E|=p+3q\hat\beta$.}
\label{tab:satsizes}
\begin{tabular}{lrrrrr}
\toprule
Size of & $p$ & $q$ & $\hat\beta$ & $n$ & $|E|$ \\
\midrule
\texttt{uf20-91} & 20 & 91 & 781 & 71\,111 & 213\,233 \\
\texttt{aim-50-1\_6} & 50 & 80 & 4\,951 & 396\,180 & 1\,188\,290 \\
\texttt{aim-100-1\_6} & 100 & 160 & 19\,901 & 3\,184\,360 & 9\,552\,580 \\
\texttt{aim-200-2\_0} & 200 & 400 & 79\,801 & 31\,920\,800 & 95\,761\,400 \\
\bottomrule
\end{tabular}
\end{table}

\section{Conclusion}
\label{sec:conclusion}
\textsc{Siriaisa} 0.0.8 returns an independent dominating set (Theorem~\ref{thm:correctness}) in $O((n+m)\,\alpha_{\mathrm A}(n))$ 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}). 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.

On the SAT-IDS graph of the solver \texttt{satypy} 0.0.4, every independent dominating set has $p$ or at least $\beta+p>2p^2$ vertices, so \texttt{satypy} answers every unsatisfiable formula correctly, every SATISFIABLE answer carries a satisfying assignment, and every answer is correct when the ratio on the graph is at most $2p$ (Theorem~\ref{thm:sat}); the bound of Theorem~\ref{thm:split} never separates satisfiable from unsatisfiable formulas (Proposition~\ref{prop:nosep}), branching on the clause named by the output is exact and polynomial for every fixed depth (Proposition~\ref{prop:branch}), and with $\beta_t=p^t(3q)^{t-1}+1$ copies every $n^{1-1/t}$-approximation decides satisfiability (Theorem~\ref{thm:satgap}), so that Conjecture~\ref{conj:sqrt} would decide every formula in polynomial time (Corollary~\ref{cor:sat}); its independent domination number determines the minimum number of falsified clauses (Theorem~\ref{thm:maxsat}), with $\beta^*$ copies its splitting excess is asymptotic to $2pL$ (Proposition~\ref{prop:satexcess}), and on $247$ small formulas every answer agrees with exhaustive search, with an optimal output on all $155$ satisfiable instances of the graph (Section~\ref{sec:satexp}).

We do not claim that \textsc{Siriaisa} has ratio $n^{3/4}$ 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.8}); 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}