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

[email protected]

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 P=NP\mathrm{P}=\mathrm{NP}P=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+Nlog⁡N+M)O(n+m+N\log N+M)O(n+m+NlogN+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 (Δ+1)/2=2.5≤3(\Delta+1)/2 = 2.5 \le 3(Δ+1)/2=2.5≤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.

Introduction

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

MIDS is much harder to approximate than the ordinary Minimum Dominating Set problem. Irving proved that, unless P=NP\mathrm{P}=\mathrm{NP}P=NP , no polynomial-time algorithm can guarantee a factor KKK for any fixed constant K>1K>1K>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 P=NP\mathrm{P}=\mathrm{NP}P=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 HHH has maximum degree Δ(H)≤4\Delta(H) \le 4Δ(H)≤4 .
3. LP-Guided MIS. Solve the LP relaxation of MIDS on HHH 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 uuu is processed, its current neighbours in the working graph are listed. The vertex uuu is removed. For each neighbour viv_ivi​ , an auxiliary vertex (u,i)(u,i)(u,i) is created and connected to viv_ivi​ ; it is also connected to the previous neighbour vi−1v_{i-1}vi−1​ cyclically.

The following Markdown painted gadget illustrates the local replacement for a vertex uuu of degree 4:

Original Component:               Auxiliary Graph (Local View):

        v_0                               v_0
      / | \                             /   \
    /   |   \                         a_0   a_1
  v_3   u   v_1        =====>         |       |
    \   |   /                         a_3   a_2
      \ | /                             \   /
        v_2                               v_2

  (u is removed)                 (a_i is the auxiliary vertex (u, i))

In the auxiliary graph, the auxiliary vertices aia_iai​ are connected to the original neighbours viv_ivi​ and vi−1v_{i-1}vi−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:

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

Because 2.5≤32.5 \le 32.5≤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 DDD satisfies:

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

Runtime Analysis

Let n=∣V∣n=|V|n=∣V∣ and m=∣E∣m=|E|m=∣E∣ for the represented graph, and let NNN and MMM be the number of vertices and edges in the auxiliary graph after the degree-four reduction. The worst running time of Siriaisa is:

where TLP(N,M)T_{\mathrm{LP}}(N,M)TLP​(N,M) is the time used by the LP solver. The components are:

• Preprocessing and isolated-vertex handling: O(n+m)O(n+m)O(n+m) .
• Degree-four transformation: O(n+m)O(n+m)O(n+m) ; every original incident edge contributes only a constant number of auxiliary incidences.
• LP relaxation solve: TLP(N,M)T_{\mathrm{LP}}(N,M)TLP​(N,M) .
• Sorting vertices by LP value: O(Nlog⁡N)O(N\log N)O(NlogN) .
• Greedy MIS sweep and verification: O(N+M)O(N+M)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 | nnn | mmm | Δ\DeltaΔ | ∣DS∣|D_S|∣DS​∣ | i(G)i(G)i(G) | Ratio |
|---|---|---:|---:|---:|---:|---:|---:|
| adv_clique_k8.dimacs | Clique K8K_8K8​ | 8 | 28 | 7 | 1 | 1 | 1.000 |
| adv_complete_bipartite_k4_4.dimacs | Complete bipartite K4,4K_{4,4}K4,4​ | 8 | 16 | 4 | 4 | 4 | 1.000 |
| adv_crown_5.dimacs | Crown graph on 10 vertices | 10 | 20 | 4 | 2 | 2 | 1.000 |
| adv_cycle_c12.dimacs | Cycle C12C_{12}C12​ | 12 | 12 | 2 | 4 | 4 | 1.000 |
| adv_double_star_4_4.dimacs | Double star DS(4,4)DS(4,4)DS(4,4) | 10 | 9 | 5 | 5 | 5 | 1.000 |
| adv_grid_3x4.dimacs | Grid 3×43\times43×4 | 12 | 17 | 4 | 4 | 4 | 1.000 |
| adv_ladder_2x5.dimacs | Ladder 2×52\times52×5 | 10 | 13 | 3 | 3 | 3 | 1.000 |
| adv_lollipop_k5_p5.dimacs | Lollipop K5K_5K5​ -- P5P_5P5​ | 10 | 15 | 5 | 3 | 3 | 1.000 |
| adv_path_p12.dimacs | Path P12P_{12}P12​ | 12 | 11 | 2 | 4 | 4 | 1.000 |
| adv_projection_fallback_6.dimacs | Projection-polarity graph | 6 | 6 | 3 | 3 | 3 | 1.000 |
| adv_ratio2_trap_7.dimacs | Ratio-2 trap | 7 | 11 | 5 | 4 | 2 | 2.000 |
| adv_star_k1_11.dimacs | Star K1,11K_{1,11}K1,11​ | 12 | 11 | 11 | 1 | 1 | 1.000 |

The largest observed exact ratio is 2.0002.0002.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)(1,2),(1,3),(1,4),(2,4),(3,4),(3,6)(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{1,2,3,4,6}1,2,3,4,6 .

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

This behaviour illustrates why Siriaisa verifies S1S_1S1​ and S2S_2S2​ in the original component before accepting them. The accepted global set 2,5,6{2,5,6}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 P=NP\mathrm{P}=\mathrm{NP}P=NP , such a universal proof would establish P=NP\mathrm{P}=\mathrm{NP}P=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.