The Furones Algorithm

An Approximate Solution to the Minimum Dominating Set Problem: The Furones Algorithm

Frank Vega

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

[e-mail]

---

Abstract

The Minimum Dominating Set problem is NP-hard and admits no polynomial-time $(1-\varepsilon)\ln n$ approximation unless $\mathrm{P}=\mathrm{NP}$ . This paper describes Furones version 0.2.9. The implementation transforms each connected component into a validated degree-four auxiliary graph, solves the LP relaxation of MDS on that auxiliary graph, uses the LP values only as tie-breakers in the standard greedy set-cover algorithm, projects the auxiliary solution back to the original component, also tests the complement, validates domination, and prunes redundant vertices. The unconditional approximation statement supported by this implementation is an $H_{\Delta+1}$ greedy set-cover guarantee for MDS on the auxiliary graph; since the auxiliary graph has $\Delta\leq4$ , this gives $H_5=137/60\approx2.2834$ on the auxiliary instance. Transferring this guarantee into a constant-factor approximation for MDS on the original graph still requires an auxiliary-to-original optimum comparison. If such a universal constant transfer theorem were proved, then Furones would break the logarithmic approximation barrier for MDS and would imply $\mathrm{P}=\mathrm{NP}$ . At present this remains a conditional implication rather than an unconditional proof of $\mathrm{P}=\mathrm{NP}$ . The new adversarial MILP experiment reports twelve verified DIMACS runs, with exact ratios between $1.000$ and $2.000$ against SciPy MILP optima.

---

Introduction

The Minimum Dominating Set (MDS) problem asks for a smallest set $D\subseteq V$ such that every vertex of an undirected graph $G=(V,E)$ either belongs to $D$ or has a neighbour in $D$ . We write $\gamma(G)$ for the optimum size.

Dominating Set is hard to approximate: the set-cover reduction gives an $O(\ln n)$ approximation, and Feige's threshold for set cover, together with the dominating-set inapproximability of Raz and Safra, implies that a polynomial-time constant-factor approximation for general MDS would force $\mathrm{P}=\mathrm{NP}$ . Consequently, any claimed constant approximation ratio for MDS must identify the precise theorem that transfers the constant bound to the original input graph.

The Furones v0.2.9 implementation has three main components.

1. It removes self-loops and selects isolated vertices.
2. For each remaining connected component $C$ , it builds a degree-four auxiliary graph $H_C$ .
3. It solves the MDS LP relaxation on $H_C$ , runs greedy set cover with LP tie-breaking, projects the auxiliary solution back to $C$ , also considers the complement of the projected set, validates domination on $C$ , and greedily prunes redundant vertices.

Let $S_C$ be the dominating set computed on the auxiliary graph $H_C$ . Since MDS is exactly set cover over closed neighbourhoods, and each closed neighbourhood in $H_C$ has size at most $\Delta(H_C)+1\leq5$ , the greedy set-cover analysis gives:

$$|S_C|\leq H_5\,\gamma(H_C) \quad\text{where}\quad H_5=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}=\frac{137}{60}<2.284.$$

This is an unconditional guarantee for the auxiliary graph. The remaining issue is the relation between the auxiliary optimum $\gamma(H_C)$ and the original optimum $\gamma(C)$ , together with the projection/complement validation step. A universal constant transfer theorem would turn the auxiliary $H_5$ guarantee into a polynomial-time constant approximation for MDS on arbitrary graphs. By the logarithmic inapproximability barrier, such a theorem would imply $\mathrm{P}=\mathrm{NP}$ .

The main contributions are:

• A code-faithful description of the Furones v0.2.9 degree-four auxiliary reduction and LP-backed greedy MDS routine.
• An unconditional correctness statement for returned outputs: whenever component validation succeeds, the algorithm returns a dominating set, and pruning preserves domination.
• An unconditional $H_5<2.284$ approximation guarantee for MDS on the degree-four auxiliary graph.
• A precise conditional implication: if the auxiliary-to-original transfer is universally bounded by a constant, then Furones is a polynomial-time constant approximation for general MDS and therefore implies $\mathrm{P}=\mathrm{NP}$ .
• An updated adversarial experiment using experiments/run_adversarial_milp.py, comparing Furones v0.2.9 against exact SciPy MILP optima on twelve DIMACS instances.

---

Research Data

The algorithm is implemented in the Python package Furones, freely available on PyPI. The current version is v0.2.9, hosted at https://github.com/frankvegadelgado/furones, with reproducible capsule at https://pypi.org/project/furones/. It is released under the MIT License, uses git for versioning, requires Python $\geq$ 3.12 with NetworkX $\geq$ 3.4.2, NumPy $\geq$ 2.2.1, and SciPy $\geq$ 1.15.0. Main entry points are asia, batch_asia, test_asia; core routine furones.algorithm.find_dominating_set.

---

Description of the Algorithm

The public routine find_dominating_set computes an approximate minimum dominating set of an undirected graph. It returns a verified dominating set and raises RuntimeError if the auxiliary projection stage cannot validate a component candidate. It rejects non-graph inputs, removes self-loops, handles isolated vertices, solves each remaining connected component separately via _find_component_solution, and prunes redundant vertices from the union of the component solutions.

FindDominatingSet $(G)$ in Furones v0.2.9:

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

Ensure: A dominating set $D\subseteq V$ , or a runtime error if candidate validation fails

1. If $G$ is not an undirected NetworkX graph, raise ValueError.
2. If $V=\emptyset$ , return $\emptyset$ .
3. Remove self-loops from a working copy of $G$ .
4. $D\gets{v:\deg(v)=0}$ (isolated vertices); remove $D$ from the working graph.
5. For each connected component $C$ of the working graph:
   • $H_C\gets\textit{DegreeFourAuxiliary}(C)$
   • $S_C\gets\textit{MdsLPGreedy}(H_C)$
   • $P_C\gets{u\in V(C):(u,i)\in S_C\text{ for some }i}$
   • $\mathcal{A}\gets{P_C,\;V(C)\setminus P_C}$ sorted by increasing cardinality
   • For $A\in\mathcal{A}$ : if $A$ dominates $C$ , set $D\gets D\cup A$ and continue to the next component.
   • Raise RuntimeError if no validated component candidate is found.
6. $D\gets\textit{PruneRedundant}(G,D)$ .
7. Return $D$ .

---

The Degree-Four Gadget

The subroutine _degree_four_auxiliary_graph builds and validates the sequential degree-four auxiliary graph. For a connected component $C$ , it replaces each original vertex $u$ with a cyclic sequence of auxiliary vertices $(u,0),(u,1),\ldots$ . Each auxiliary vertex is attached to one current neighbour of $u$ , and consecutive neighbours are linked through the sequence. The implementation then validates that the maximum degree of the auxiliary graph is at most four and raises RuntimeError with message "Degree-four reduction failed: max degree is {max_degree}, expected <= 4." if this invariant fails.

Local Furones degree-four gadget for a vertex $u$ with four current neighbours. The original vertex is removed and replaced by auxiliary vertices $(u,i)$ ; each auxiliary vertex connects to one current neighbour and to the previous current neighbour, with the last edge closing the cycle.

DegreeFourAuxiliary $(C)$ :

Require: Connected component $C$

Ensure: Auxiliary graph $H$ with maximum degree at most $4$

1. $H\gets C.\text{copy}()$ .
2. For each $u\in V(C)$ :
   • $N\gets$ current neighbours of $u$ in $H$ ; remove $u$ from $H$ .
   • Set $a_{\mathrm{first}}\gets\bot$ and $p\gets\bot$ .
   • For $i=0,1,\ldots,|N|-1$ with neighbour $v=N_i$ : add auxiliary vertex $a=(u,i)$ and edge ${a,v}$ ; if $p=\bot$ set $a_{\mathrm{first}}\gets a$ , else add edge ${a,p}$ ; set $p\gets v$ .
   • If $|N|>1$ , add edge ${a_{\mathrm{first}},p}$ .
3. If $\Delta(H)>4$ , raise RuntimeError.
4. Return $H$ .

---

LP-Backed Greedy MDS

This module targets MDS directly and does not impose independence. The input graphs produced by the Furones auxiliary reduction are expected to have maximum degree at most 4, so every closed neighbourhood has size at most 5. The greedy set-cover algorithm therefore has the standard $H_{\Delta+1}$ approximation bound on those bounded-degree instances; for $\Delta\leq4$ this is $H_5\approx2.283$ .

The auxiliary solver first solves the LP relaxation of unweighted MDS (MDS-LP):

$$\begin{array}{ll} \min & \displaystyle\sum_{v\in V(H)} x_v \ \text{s.t.} & \displaystyle\sum_{u\in N_H[v]}x_u\geq 1 \qquad \forall v\in V(H),\ & 0\leq x_v\leq 1 \qquad \forall v\in V(H). \end{array}$$

If the LP solve fails, the implementation falls back to $x_v=1$ for all $v$ , which is always feasible; this fallback is used only for priority tie-breaking and diagnostics. The fractional values are then used only as a tie-breaker in the greedy set-cover routine greedy_mds_from_lp_priority: while some vertex remains uncovered, the routine chooses a vertex whose closed neighbourhood covers the largest number of uncovered vertices, breaking ties by larger LP value, degree, and a stable representation of the vertex. After the greedy pass, the auxiliary solution is pruned by prune_redundant_vertices, which deletes any selected vertex whose removal preserves domination.

---

Correctness of Returned Solutions

A selected vertex $v$ is removable by prune_redundant_vertices_dominating when another selected vertex dominates $v$ , and every neighbour of $v$ remains dominated after $v$ is deleted.

Theorem 1 (Feasibility). Whenever FindDominatingSet returns, its output is a dominating set of the input graph.

Proof. Isolated vertices are placed in $D$ , so they dominate themselves. For every non-isolated connected component $C$ , the algorithm considers the projected auxiliary solution $P_C$ and its complement $V(C)\setminus P_C$ . It adds a candidate only after directly verifying that the candidate dominates $C$ . If neither candidate dominates $C$ , the implementation raises an error rather than returning an invalid set. A vertex $v\in D$ is removed by pruning only if $v$ has another neighbour in the current set $D$ and every neighbour of $v$ either belongs to $D$ or has at least two neighbours in $D$ ; each such pruning step preserves domination. Therefore the final returned set dominates $G$ . $\square$

---

Approximation Ratio and the Logarithmic Barrier

Let $H_k=\sum_{j=1}^{k}\frac{1}{j}$ denote the $k$ th harmonic number.

Theorem 2 (Auxiliary degree-four MDS guarantee). Let $H$ be an auxiliary graph produced by DegreeFourAuxiliary, and let $S$ be the dominating set returned by MdsLPGreedy on $H$ . Then:

$$|S|\leq H_{\Delta(H)+1}\,\gamma(H)\leq H_5\,\gamma(H)=\frac{137}{60}\,\gamma(H).$$

Proof. MDS is the set-cover instance whose universe is $V(H)$ and whose sets are the closed neighbourhoods $N_H[v]$ . Greedy set cover returns a cover within a factor $H_b$ of optimum, where $b$ is the maximum set size. Here $b\leq\Delta(H)+1$ . The construction validates $\Delta(H)\leq4$ , so $b\leq5$ and the final bound is $H_5=137/60$ . The LP values are used only for tie-breaking and do not weaken the greedy set-cover guarantee. $\square$

The projection step creates $P_C={u\in V(C):(u,i)\in S_C\text{ for some }i}$ . Since projection can identify several auxiliary vertices with the same original vertex, $|P_C|\leq|S_C|$ . To obtain a constant approximation for original MDS, one needs a transfer statement relating the auxiliary optimum to the original optimum.

Assumption (Auxiliary MDS/MDS transfer). There is a universal constant $\alpha$ such that, for every connected component $C$ processed by Furones v0.2.9, the corresponding auxiliary graph and validation step satisfy:

$$|D_C|\leq H_5\,\alpha\,\gamma(C),$$

where $D_C$ is the validated component solution returned after projection/complement selection.

Proposition (Conditional ratio). Under the auxiliary MDS/MDS transfer assumption, Furones is an $H_5\alpha$ -approximation for Minimum Dominating Set.

Proof. Summing over connected components gives $|D|\leq\sum_C H_5\,\alpha\,\gamma(C)$ . Since Minimum Dominating Set is additive over connected components, $\sum_C\gamma(C)=\gamma(G)$ . Pruning can only decrease $|D|$ . Hence $|D|\leq H_5\alpha\,\gamma(G)$ . $\square$

Theorem 3 (Conditional implication for $\mathrm{P}$ vs $\mathrm{NP}$ ). If Furones v0.2.9 satisfies a universal constant approximation ratio for MDS, then $\mathrm{P}=\mathrm{NP}$ .

Proof. For any fixed constant $\rho$ , a polynomial-time $\rho$ -approximation for MDS beats $(1-\varepsilon)\ln n$ on all sufficiently large inputs. This contradicts the Feige/Raz–Safra logarithmic inapproximability threshold for dominating set unless $\mathrm{P}=\mathrm{NP}$ . Therefore a proven universal constant approximation ratio for Furones would imply $\mathrm{P}=\mathrm{NP}$ . $\square$

Theorem 3 is conditional. The present implementation proves the auxiliary $H_5$ MDS guarantee and validates returned dominating sets, but it does not by itself prove the auxiliary-to-original transfer needed for an unconditional theorem.

---

Runtime Analysis

Theorem 4 (Runtime). Let $n=|V(G)|$ and $m=|E(G)|$ , and let $N$ and $M$ be the total numbers of vertices and edges in the auxiliary instances. The implemented runtime is polynomial and is bounded by:

$$O\bigl(n+m+T_{\mathrm{LP}}(N,M)+N^2(\Delta+1)+|D|(n+m)\bigr),$$

where $T_{\mathrm{LP}}$ is the time used by SciPy's LP solver and $\Delta\leq4$ on the auxiliary graphs.

Proof sketch. Self-loop removal, isolate detection, connected-component traversal, and auxiliary construction are linear in the input and auxiliary sizes. The current Python greedy routine scans all auxiliary vertices at each selection step and computes uncovered closed-neighbourhood intersections, giving the displayed $N^2(\Delta+1)$ bound. The LP relaxation is delegated to SciPy's linprog with HiGHS, called with method="highs" and options={"presolve": True}. The final pruning step calls domination checks after candidate deletions. No exponential subroutine is used by the approximation path. $\square$

---

Experiments

Adversarial MILP Setup

The repository contains an adversarial DIMACS suite under experiments/. The runner is experiments/run_adversarial_milp.py. It compares the core Furones routine against an exact binary MILP formulation of MDS using SciPy. Each MILP variable $x_v\in{0,1}$ records whether $v$ is selected, and each domination constraint enforces:

$$\sum_{u\in N[v]}x_u\geq 1.$$

Both solutions are checked with networkx.dominating.is_dominating_set. The command used was:

python -B experiments\run_adversarial_milp.py

Results

Instance	$n$	$m$	$\Delta$	$\lvert D_F\rvert$	$\gamma$	Ratio	$T_F$ (ms)	$T_M$ (ms)
adv_clique_k8	8	28	7	1	1	1.000	15.639	15.084
adv_complete_bipartite_k4_4	8	16	4	4	2	2.000	12.031	22.177
adv_crown_5	10	20	4	2	2	1.000	10.909	20.829
adv_cycle_c12	12	12	2	4	4	1.000	8.169	26.572
adv_double_star_4_4	10	9	5	2	2	1.000	6.340	2.619
adv_grid_3x4	12	17	4	4	4	1.000	9.565	23.117
adv_ladder_2x5	10	13	3	4	3	1.333	9.055	21.615
adv_lollipop_k5_p5	10	15	5	3	3	1.000	7.167	37.298
adv_path_p12	12	11	2	4	4	1.000	6.254	24.738
adv_projection_fallback_6	5	6	3	2	2	1.000	5.673	27.490
adv_ratio2_trap_7	7	11	5	2	2	1.000	5.373	1.935
adv_star_k1_11	12	11	11	1	1	1.000	6.223	2.124

$D_F$ is the set returned by Furones, $\gamma$ is the exact optimum from SciPy MILP, $T_F$ is Furones time in milliseconds, and $T_M$ is MILP time in milliseconds.

All twelve returned sets passed domination validation. Ten instances were solved optimally by Furones. The two non-optimal cases have ratios $1.333$ and $2.000$ . Summary values: worst exact ratio $2.000$ , mean ratio $1.111$ , median ratio $1.000$ , total Furones time $102.398$ ms, total exact MILP time $225.598$ ms. The observed worst case is below $H_5$ on this suite, but that remains an empirical statement about these original inputs; the proved $H_5$ bound applies to the auxiliary graph.

---

Conclusion

Furones v0.2.9 now implements a degree-four auxiliary reduction followed by LP-backed greedy MDS and validated projection/complement selection. The auxiliary approximation theorem is the standard greedy set-cover bound $H_{\Delta+1}$ , which becomes $H_5=137/60<2.284$ on the validated degree-four auxiliary graphs.

The remaining theoretical issue is the transfer from auxiliary MDS to original MDS through projection and complement validation. A universal constant transfer would make Furones a polynomial-time constant approximation for MDS and would therefore imply $\mathrm{P}=\mathrm{NP}$ by the logarithmic inapproximability barrier. The present paper records that implication explicitly while avoiding an unconditional claim not yet proved by the code or by the current analysis. Future work should focus on proving or refuting the required auxiliary-to-original transfer inequality and on expanding the adversarial MILP suite beyond the twelve current DIMACS instances.