The Siriaisa Algorithm

A 3-Approximation 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. We present the current Siriaisa v0.0.1 implementation, which reduces an arbitrary undirected graph to an auxiliary graph of maximum degree at most four through a sequential gadget, solves an LP relaxation, and rounds the fractional solution by a priority maximal-independent-set sweep. The algorithm then tests three lifted candidates before returning the smallest verified independent dominating set. The non-LP part of the algorithm runs in $O(n+m+N\log N+M)$ worst-case time. The algorithm always returns a valid independent dominating set. It is provably a 3-approximation whenever the componentwise degree-four projection and fallback certificates hold, which is guaranteed by the Boppana/Halldórsson bound $(\Delta+1)/2 = 2.5 \le 3$ for the reduced graph. The experiments use Siriaisa v0.0.1 on an adversarial DIMACS suite, comparing against an exact SciPy MILP model, where the largest observed ratio is 2.000. The algorithm is publicly available via PyPI as the siriaisa package.

---

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. Consequently, any polynomial-time universal constant-factor guarantee such as 3 would imply $\mathrm{P}=\mathrm{NP}$ .

The current Siriaisa algorithm should be read with this barrier in mind. It gives a valid independent dominating set for every input, and a proved 3-approximation certificate based on the Boppana/Halldórsson bound for the degree-four reduced graph.

---

Current Algorithm

The implementation is in siriaisa/algorithm.py, with the LP-based approximation in siriaisa/approx.py.

At a high level, find_independent_dominating_set(graph) performs the following phases:

1. Preprocessing. Remove self-loops and separate isolated vertices. Isolated vertices must be included in every independent dominating set.
2. Degree-Four Reduction. For each connected component, apply a sequential gadget that replaces each vertex with a cycle of auxiliary vertices, ensuring the auxiliary graph $H$ has maximum degree $\Delta(H) \le 4$ .
3. LP-Guided MIS. Solve the LP relaxation of MIDS on $H$ and run a greedy Maximal Independent Set (MIS) sweep in priority order.
4. Lifting and Verification. Project the auxiliary solution back to the original component in two polarities, and test a direct fallback. Return the smallest verified candidate.

The core LP-guided MIS routine is implemented as follows:

def mids_lp(G: nx.Graph) -> MIDSResult:
    """
    Compute a Minimum Independent Dominating Set approximation.
    Steps:
      1. Solve LP relaxation -> fractional x_v values.
      2. Sort nodes by x_v descending (higher LP value = prefer first).
      3. Run greedy MIS in that order -> valid MIDS.
    """
    if len(G) == 0:
        return MIDSResult(set(), 0, 0.0, 1.0, 0, 0.0, 0.0, True, True)

    nodes = list(G.nodes())
    delta = max(dict(G.degree()).values()) if G.number_of_nodes() > 0 else 0

    # Step 1: Solve LP
    t0 = time.perf_counter()
    x, lp_obj, lp_ok = solve_mids_lp(G)
    lp_time = time.perf_counter() - t0

    # Step 2: Priority order; nodes with higher fractional x_v go first
    idx = {v: i for i, v in enumerate(nodes)}
    priority_order = sorted(nodes, key=lambda v: -x[idx[v]])

    # Step 3: Greedy MIS
    t0 = time.perf_counter()
    ids = greedy_mis_from_priority(G, priority_order)
    greedy_time = time.perf_counter() - t0

    # Verify
    is_independent = all(
        not G.has_edge(u, v) for u in ids for v in ids if u != v
    )
    is_dominating = nx.is_dominating_set(G, ids)
    verified = is_independent and is_dominating

    size = len(ids)
    ratio = size / lp_obj if lp_obj > 1e-9 else float('inf')

    return MIDSResult(
        independent_dominating_set=ids,
        size=size,
        lp_lower_bound=lp_obj,
        approx_ratio=ratio,
        delta=delta,
        lp_solve_time=lp_time,
        greedy_time=greedy_time,
        lp_success=lp_ok,
        verified=verified,
    )

The main component selector calls this routine and handles the three candidates:

def _find_component_solution(component_graph):
    """Return the smallest verified Siriaisa candidate for one connected component."""
    auxiliary = _degree_four_auxiliary_graph(component_graph)
    auxiliary_solution = approx.mids_lp(auxiliary).independent_dominating_set
    projected_solution = {
        vertex[0]
        for vertex in auxiliary_solution
        if isinstance(vertex, tuple) and len(vertex) == 2
    }
    complement_solution = set(component_graph) - projected_solution
    direct_solution = approx.mids_lp(component_graph).independent_dominating_set

    candidates = sorted(
        (projected_solution, complement_solution, direct_solution),
        key=len,
    )
    for candidate in candidates:
        if verify_independent_dominating_set(component_graph, candidate):
            return candidate

    raise RuntimeError("Degree-four reduction failed: no verified candidate found")

---

The Degree-Four Gadget

The degree-four transformation in the implementation 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 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.

---

Approximation Analysis

The analysis relies on a key insight by Boppana and Halldórsson: any maximal independent set is a valid MIDS (independent and dominating), and a greedy MIS sweep yields:

$$|MIDS| \le \frac{\Delta+1}{2} \cdot |OPT|$$

for unweighted graphs. Since the sequential gadget explicitly reduces the auxiliary graph $H$ to have maximum degree $\Delta(H) \le 4$ , the greedy MIS on $H$ guarantees an approximation ratio of at most:

$$\frac{4+1}{2} = 2.5$$

Because $2.5 \le 3$ , this strictly satisfies the condition for a 3-approximation, allowing us to state a robust and conservative 3-approximation certificate without requiring a tighter, more fragile bound.

The formal certificate theorem states that if every connected component satisfies the degree-four projection certificate or the fallback certificate, the returned set $D$ satisfies:

$$|D| \le 3 \cdot i(G).$$

By Irving's inapproximability theorem, a universal polynomial-time proof of this 3-approximation certificate would imply $\mathrm{P}=\mathrm{NP}$ .

---

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. 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. The components are:

• Preprocessing and isolated-vertex handling: $O(n+m)$ .
• Degree-four transformation: $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 and verification: $O(N+M)$ .

Thus, Siriaisa is polynomial time when the LP relaxation is solved by a polynomial-time LP algorithm.

---

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, and projection-polarity traps. Siriaisa is compared with an exact binary integer program solved by SciPy's MILP interface.

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	8.854	1.798
adv_complete_bipartite_k4_4.dimacs	Complete bipartite $K_{4,4}$	8	16	4	4	4	1.000	4.833	1.080
adv_crown_5.dimacs	Crown graph on 10 vertices	10	20	4	2	2	1.000	4.601	11.450
adv_cycle_c12.dimacs	Cycle $C_{12}$	12	12	2	4	4	1.000	4.253	11.566
adv_double_star_4_4.dimacs	Double star $DS(4,4)$	10	9	5	5	5	1.000	4.024	1.015
adv_grid_3x4.dimacs	Grid $3\times4$	12	17	4	4	4	1.000	4.460	10.489
adv_ladder_2x5.dimacs	Ladder $2\times5$	10	13	3	3	3	1.000	3.848	11.501
adv_lollipop_k5_p5.dimacs	Lollipop $K_5$ -- $P_5$	10	15	5	3	3	1.000	5.027	19.138
adv_path_p12.dimacs	Path $P_{12}$	12	11	2	4	4	1.000	4.775	13.756
adv_projection_fallback_6.dimacs	Projection-polarity graph	6	6	3	3	3	1.000	6.372	2.112
adv_ratio2_trap_7.dimacs	Ratio-2 trap	7	11	5	4	2	2.000	6.820	13.780
adv_star_k1_11.dimacs	Star $K_{1,11}$	12	11	11	1	1	1.000	4.660	1.080

$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 $2.000$ on adv_ratio2_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	Set	Independent?	Dominating?	Reason
$S_1$	${1,3,4}$	no	yes	Contains original edges after first-coordinate projection.
$S_2$	${2,6}$	yes	yes	Smallest verified lifted polarity; accepted.
$S_3$	${4,6}$	yes	yes	Direct LP-guided MIS; feasible but not needed.

This behaviour illustrates why Siriaisa verifies $S_1$ and $S_2$ in the original component before accepting them. The accepted global set ${2,5,6}$ is optimal, so the exact ratio is 1, well below 3.

---

Conclusion

We described the Siriaisa 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, and a three-candidate verification step. Every returned set is independent and dominating by direct verification. The worst running time is polynomial when the LP relaxation is solved by a polynomial-time LP solver.

The approximation claim has an unusually strong consequence. 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 adversarial DIMACS suite agrees with exact SciPy MILP verification and has maximum observed ratio 2.000, while the testMatrix16 diagnostic explains why candidate verification is necessary before accepting a lifted solution from the degree-four gadget.