The Siriaisa Algorithm

A Conditional 3-Approximation Certificate for Independent Dominating Sets: The Siriaisa Algorithm

Frank Vega

Information Physics Institute, 840 W 67th St, Hialeah, FL 33012, USA

[e-mail]

---

Abstract

The Minimum Independent Dominating Set problem (MIDS), equivalently the problem of finding a smallest maximal independent set, is a strongly inapproximable graph optimisation problem: unless $\mathrm{P}=\mathrm{NP}$ , no polynomial-time algorithm can approximate it within any fixed constant factor greater than one. This manuscript gives a source-faithful formalisation of Siriaisa v0.0.2, the unweighted MIDS algorithm implemented in the mids repository and distributed as the siriaisa package. Siriaisa removes isolated vertices, processes each connected component independently, applies a sequential degree-four gadget, solves an LP relaxation, rounds the fractional solution by a priority maximal-independent-set sweep, repairs the two lifted vertex seeds into maximal independent sets, and then returns the smallest verified independent dominating set among the repaired lifted candidates and the direct fallback. We prove the unconditional part of the implementation, namely that every returned set is independent and dominating, and we analyse the worst running time as $O(n+m+N\log N+M+T_{\mathrm{LP}}(N,M))$ , where $N$ and $M$ are the size parameters of the auxiliary LP instance. We do not claim an unconditional 3-approximation theorem from the LP ordering or from the degree-four projection. Instead, the approximation analysis is stated as a conditional certificate theorem: if every component has an independently proved local 3-certificate for the repaired lifted candidate or for the fallback candidate, then Siriaisa is a 3-approximation. This formulation makes the missing proof obligations explicit. By Irving's inapproximability theorem, a universal polynomial-time proof of those certificates would imply $\mathrm{P}=\mathrm{NP}$ . We complement the formal analysis with a reproducible adversarial DIMACS suite covering paths, cycles, stars, cliques, complete bipartite graphs, crown graphs, double stars, grids, ladders, lollipop graphs, and projection-polarity traps; all instances are small enough to compare against an exact SciPy MILP model, and the largest observed ratio is 1.500.

---

Introduction

An independent dominating set of an undirected graph $G=(V,E)$ is a set $D\subseteq V$ that is both independent and dominating: no two vertices of $D$ are adjacent, and every vertex of $V\setminus D$ has at least one neighbour in $D$ . Equivalently, $D$ is a maximal independent set. The Minimum Independent Dominating Set problem asks for such a set of minimum cardinality, denoted $i(G)$ .

MIDS is much harder to approximate than the ordinary Minimum Dominating Set problem. Irving proved that, unless $\mathrm{P}=\mathrm{NP}$ , no polynomial-time algorithm can guarantee a factor $K$ for any fixed constant $K>1$ . Halldórsson later strengthened the lower bound for the equivalent minimum maximal independent set formulation. Thus a polynomial-time 3-approximation for MIDS is not merely a new approximation result: combined with the known hardness theorem, it would imply $\mathrm{P}=\mathrm{NP}$ .

This paper documents the current unweighted implementation in the mids repository, called Siriaisa. The algorithm is built around three ideas.

1. It uses an LP relaxation of unweighted MIDS, with domination constraints on closed neighbourhoods and independence constraints on edges.
2. It reduces an arbitrary component to an auxiliary graph whose maximum degree is checked to be at most four, then rounds the LP solution by a priority maximal-independent-set sweep.
3. It lifts the reduced solution back to the original component in two polarities, repairs both lifted vertex seeds into maximal independent sets, and compares them with the LP-guided maximal independent set on the original component.

The implementation repairs and validates every candidate before returning it. This is important because the degree-four gadget may produce a valid independent dominating set in the auxiliary graph whose first-coordinate projection is no longer independent in the original graph.

---

Research Data

The implementation is the Python package siriaisa, available from the source repository. The current code version is v0.0.2, hosted at https://github.com/frankvegadelgado/mids. The package name is siriaisa, released under the MIT License, using git for versioning, and requiring Python $\geq$ 3.12 with NetworkX, NumPy, and SciPy.

---

Description of the Algorithm

Let $N[v]={v}\cup{u:(u,v)\in E}$ denote the closed neighbourhood of $v$ . The LP relaxation used by siriaisa.approx.solve_mids_lp is:

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 58: …m_{v\in V} x_v \̲[̲6pt] \text{s.t.…

The rounded solution orders vertices by decreasing LP value and then performs the standard greedy maximal-independent-set sweep (LPGuidedMIS):

Require: Undirected graph $G=(V,E)$

Ensure: A maximal independent set $S$ , hence an independent dominating set

1. If $V=\emptyset$ , return $\emptyset$ .
2. Solve the LP relaxation above and obtain fractional vector $x$ .
3. Let $\pi$ be the vertices of $G$ sorted by decreasing $x_v$ .
4. Set $S\gets\emptyset$ , $X\gets\emptyset$ .
5. For each $v\in\pi$ : if $v\notin X$ , set $S\gets S\cup{v}$ and $X\gets X\cup{v}\cup N(v)$ .
6. Return $S$ .

The degree-four transformation is sequential. When an original vertex $u$ is processed, its current neighbours in the working graph are listed as $L=(v_0,\ldots,v_{k-1})$ . The vertex $u$ is removed. For each $v_i$ an auxiliary vertex $(u,i)$ is created and connected to $v_i$ ; it is also connected to $v_{i-1}$ for $i>0$ , while $(u,0)$ is connected to $v_{k-1}$ when $k>1$ .

The full component selector (Siriaisa) proceeds as follows after the degree-four LP solve: the auxiliary solution is projected by first coordinates to obtain seed $P_1$ , its complement $P_2=V(C)\setminus P_1$ is formed, and both lifted vertex sets are passed to RepairToMaximalIndependentSet. The repair sweep scans the seed vertices first and then the remaining component vertices in graph order, adding a vertex exactly when no previously selected neighbour blocks it. The repaired sets $S_1$ and $S_2$ are therefore maximal independent sets before the final size selection. The direct LP-guided solution $S_3$ on the original component is kept as a third feasible candidate. The smallest verified candidate among $S_1,S_2,S_3$ is returned for the component.

---

The Degree-Four Gadget

The diagram below shows the local replacement for $k=5$ . The same cyclic pattern is used for every current degree $k$ . Each auxiliary vertex $a_i=(u,i)$ is adjacent to $v_i$ and to $v_{i-1}$ , with indices taken cyclically:

In the auxiliary graph the auxiliary vertices $a_i$ are connected to the original neighbours $v_i$ and $v_{i-1}$ . This cyclic interleaving ensures that the maximum degree of any vertex in the auxiliary graph is strictly bounded by 4, which is verified at runtime.

---

Correctness of the Algorithm

Theorem (Feasibility). For every input graph whose vertex set is represented in the graph object, the Siriaisa algorithm returns an independent dominating set.

Proof. Self-loops do not affect domination and cannot help independence, so they may be removed. Each isolated vertex must belong to every independent dominating set, because it has no neighbour that can dominate it. Thus adding all isolated vertices to $D$ is forced and cannot create an edge inside $D$ . For a non-isolated connected component $C$ , candidates $S_1$ and $S_2$ are produced by the repair routine, which starts with an empty set and adds a vertex only when no previously selected neighbour blocks it; the repaired set is therefore independent, maximal, and dominating. The fallback $S_3$ is produced by the LP-guided greedy sweep and is likewise independent and dominating. The implementation verifies each candidate before returning it. Different connected components have no edges between them, so the union over components, together with the isolated vertices, is independent and dominating for the whole graph. $\square$

---

Runtime Analysis

Let $n=|V|$ and $m=|E|$ for the input graph, and let $N$ and $M$ be the number of vertices and edges in the auxiliary graph after the degree-four reduction. In the sequential gadget every original incident edge contributes only a constant number of auxiliary incidences, so $N,M=O(n+m)$ .

Theorem (Worst running time). The worst running time of Siriaisa is:

$$O\bigl(n+m+N\log N+M+T_{\mathrm{LP}}(N,M)\bigr),$$

where $T_{\mathrm{LP}}(N,M)$ is the time used by the LP solver on an LP with $N$ variables and $N+M$ linear constraints. Since $N,M=O(n+m)$ , Siriaisa is polynomial time when the LP relaxation is solved by a polynomial-time LP algorithm.

The components are:

• Preprocessing and isolated-vertex handling: $O(n+m)$ .
• Degree-four transformation: $O(N+M)=O(n+m)$ ; every original incident edge contributes only a constant number of auxiliary incidences.
• LP relaxation solve: $T_{\mathrm{LP}}(N,M)$ .
• Sorting vertices by LP value: $O(N\log N)$ .
• Greedy MIS sweep, two repair sweeps, and verification: $O(N+M)$ .

---

Approximation Certificates and the Consequence for P vs NP

The proof separates two statements. First, the feasibility theorem is unconditional: the returned set is always a valid independent dominating set. Second, a 3-approximation ratio requires additional size inequalities that the implementation does not by itself prove.

The LP-guided routine always returns a maximal independent set. The LP values only determine the greedy order; no claim is made that this ordering has a bounded approximation ratio for MIDS. Similarly, the degree-four auxiliary construction guarantees only the checked degree bound $\Delta(H)\leq 4$ and the availability of lifted seeds. It does not, without a separate proof, imply that $i(H)$ is comparable to $i(C)$ , nor that a repaired projection has size controlled by the auxiliary solution.

Definition (Local 3-certificate). Let $C$ be a connected component processed by Siriaisa and let $S_C$ be the candidate selected for that component after repair and verification. A local 3-certificate for $C$ is an independent proof of:

$$|S_C|\leq 3\,i(C).$$

Definition (Sufficient structural certificate). Let $H$ be the degree-four auxiliary graph for $C$ , let ParseError: KaTeX parse error: Undefined control sequence: \textsc at position 3: A=\̲t̲e̲x̲t̲s̲c̲{LPGuidedMIS}(H… , and let $S_1,S_2,S_3$ be the three candidates. A sufficient structural certificate for a repaired lifted candidate $S_j$ , $j\in{1,2}$ , is a proof of:

$$|S_j|\leq |A|,\qquad |A|\leq \rho\, i(H),\qquad i(H)\leq \kappa\, i(C),$$

with $\rho\kappa\leq 3$ . A sufficient structural certificate for the fallback is a proof of $|S_3|\leq 3\,i(C)$ . These are certificate obligations, not consequences of feasibility verification.

Theorem (Conditional 3-approximation). If every connected component processed by Siriaisa has a local 3-certificate, then the returned set $D$ satisfies:

$$|D|\leq 3\,i(G).$$

Proof. Let $C_1,\ldots,C_q$ be the non-isolated connected components and $I$ the isolated-vertex set. Isolated vertices are forced into every independent dominating set, so $i(G)=|I|+\sum_{r=1}^q i(C_r)$ . For each component the accepted candidate $S_r$ satisfies $|S_r|\leq 3\,i(C_r)$ by assumption. Therefore:

$$|D|=|I|+\sum_{r=1}^q |S_r| \leq |I|+3\sum_{r=1}^q i(C_r) \leq 3!\left(|I|+\sum_{r=1}^q i(C_r)\right) =3\,i(G). \quad\square$$

Theorem (Implication for $\mathrm{P}$ versus $\mathrm{NP}$ ). If Siriaisa is a polynomial-time 3-approximation for MIDS on all finite undirected graphs, then $\mathrm{P}=\mathrm{NP}$ .

Proof. Irving proved that, unless $\mathrm{P}=\mathrm{NP}$ , no polynomial-time approximation algorithm for MIDS can guarantee a factor $K$ for any fixed constant $K>1$ . A 3-approximation is such a fixed-constant approximation with $K=3$ . Therefore the existence of a universal polynomial-time 3-approximation contradicts Irving's theorem unless $\mathrm{P}=\mathrm{NP}$ . $\square$

---

Experiments

The repository's experiments directory contains an adversarial suite of small DIMACS graphs. The instances are targeted structural tests for the mechanisms used by Siriaisa, including sparse low-degree graphs, dense graphs, bipartite extremal graphs, graphs where $i(G)$ is much larger than the ordinary domination number, and projection-polarity traps. Siriaisa is compared with an exact binary integer program solved by SciPy's MILP interface. The exact MIDS model is:

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 58: …m_{v\in V} x_v \̲[̲6pt] \text{s.t.…

Adversarial DIMACS results

DIMACS file	Graph class	$n$	$m$	$\Delta$	$\lvert D_S\rvert$	$i(G)$	$\lvert D_S\rvert/i(G)$	$T_S$ (ms)	$T_M$ (ms)
adv_clique_k8.dimacs	Clique $K_8$	8	28	7	1	1	1.000	12.953	2.047
adv_complete_bipartite_k4_4.dimacs	Complete bipartite $K_{4,4}$	8	16	4	4	4	1.000	7.944	1.887
adv_crown_5.dimacs	Crown graph on 10 vertices	10	20	4	2	2	1.000	5.311	14.325
adv_cycle_c12.dimacs	Cycle $C_{12}$	12	12	2	4	4	1.000	9.465	21.537
adv_double_star_4_4.dimacs	Double star $DS(4,4)$	10	9	5	5	5	1.000	8.112	3.408
adv_grid_3x4.dimacs	Grid $3\times4$	12	17	4	4	4	1.000	6.130	19.024
adv_ladder_2x5.dimacs	Ladder $2\times5$	10	13	3	3	3	1.000	10.611	21.224
adv_lollipop_k5_p5.dimacs	Lollipop $K_5$ -- $P_5$	10	15	5	3	3	1.000	11.793	44.706
adv_path_p12.dimacs	Path $P_{12}$	12	11	2	4	4	1.000	6.724	21.260
adv_projection_fallback_6.dimacs	Projection-polarity graph	6	6	3	3	3	1.000	9.433	2.153
adv_ratio15_trap_7.dimacs	Ratio-1.5 trap	7	11	5	3	2	1.500	5.039	20.796
adv_star_k1_11.dimacs	Star $K_{1,11}$	12	11	11	1	1	1.000	6.391	1.144

$D_S$ is the set returned by Siriaisa, $i(G)$ is the exact optimum from SciPy MILP, $T_S$ is Siriaisa time in milliseconds, and $T_M$ is MILP time in milliseconds. Every Siriaisa and MILP set was independently verified as an independent dominating set.

The largest observed exact ratio is $1.500$ on adv_ratio15_trap_7.dimacs. This instance is included precisely because it is not solved optimally by the present implementation, and therefore it tests the approximation claim more seriously than a table of only optimal outcomes. The remaining adversarial classes are solved optimally in this run.

---

Diagnostic: testMatrix16

The file benchmarks/testMatrix16 has DIMACS header p edge 6 6 and edge lines $(1,2),(1,3),(1,4),(2,4),(3,4),(3,6)$ . Vertex 5 is isolated, so it is forced into every independent dominating set. The non-isolated component is induced by ${1,2,3,4,6}$ .

Running the internal three-candidate selector on the non-isolated component yields:

Candidate	Raw seed	Repaired set	Independent?	Dominating?	Reason
$S_1$	${1,3,4}$	${1,6}$	yes	yes	The raw projection is not independent, but repair keeps 1 and then adds 6.
$S_2$	${2,6}$	${2,6}$	yes	yes	The complement seed is already a maximal independent set of the component.
$S_3$	${4,6}$	${4,6}$	yes	yes	The direct LP-guided maximal independent set is feasible.

This behaviour is no longer a feasibility problem for either lifted polarity. The repair step fixes feasibility, but feasibility alone is not an approximation-ratio proof. On this instance all three repaired component candidates have size 2. The implementation's stable ordering returns the repaired $S_1$ , and after adding isolated vertex 5 the global output is ${1,5,6}$ . This set is optimal, so the exact ratio is 1, well below 3.

---

Conclusion

We described the Siriaisa v0.0.2 implementation for unweighted Minimum Independent Dominating Set. The algorithm combines isolated-vertex preprocessing, a sequential degree-four gadget, an LP relaxation, LP-guided maximal-independent-set rounding, repair of the two lifted vertex seeds into maximal independent sets, and a three-candidate verification step. Every returned set is independent and dominating because all three component candidates are maximal independent sets before selection and because the implementation still performs explicit verification. The worst running time is polynomial when the LP relaxation is solved by a polynomial-time LP solver.

The approximation claim is conditional: if the component certificates hold universally, Siriaisa is a polynomial-time 3-approximation for MIDS. Since MIDS admits no fixed-constant polynomial-time approximation unless $\mathrm{P}=\mathrm{NP}$ , such a universal proof would establish $\mathrm{P}=\mathrm{NP}$ . The present manuscript does not supply that universal proof. The adversarial DIMACS suite agrees with exact SciPy MILP verification and has maximum observed ratio 1.500, while the testMatrix16 diagnostic explains why lifted seeds are repaired before selection.