Furones: Approximate Dominating Set Solver

This work builds upon The Furones Algorithm.

Overview of the Minimum Dominating Set (MDS)

Definition

A dominating set in a graph $G = (V, E)$ is a subset $D \subseteq V$ such that every vertex not in $D$ is adjacent to at least one vertex in $D$. The minimum dominating set (MDS) is the smallest possible dominating set in terms of the number of vertices.

Computational Complexity

• NP-Hard: Finding the minimum dominating set is NP-hard; no polynomial-time exact algorithm is known for general graphs.
• Approximation: The greedy Set Cover heuristic gives a ratio $H(\Delta+1) \le 1 + \ln(\Delta+1) = \mathcal{O}(\log \Delta)$, where $\Delta$ is the maximum degree. This is tight and matches the $o(\ln n)$-in-$n$ inapproximability threshold (Dinur–Steurer).

Applications

• Network monitoring and wireless sensor coverage
• Influence maximisation in social networks
• Facility placement and logistics
• Protein–protein interaction modelling

The Furones Algorithm

Furones v0.3.8 is a linear-time candidate-comparison solver for MDS. It builds a portfolio of dominating-set candidates on the input graph and returns the smallest validated one.

New in v0.3.8: a max-cut double-cover candidate ($C_X$) — it computes an exact min-side maximum cut of the bipartite double cover of the working graph and decodes it into a validated dominating-set candidate (see below). The pseudocode, gadget, correctness, and runtime are documented in the manuscript.

The pipeline consists of:

1. Preprocessing: self-loop removal, isolated-vertex separation.
2. TSCC-style pendant cascade (ReduceToTSCCForDS): iteratively commits pendant supports and isolated vertices to a forced set $F$, producing a reduced residual.
3. Baker-style reduced solve on the residual (treated as planar by construction): used only as a validated candidate generator — its output enters the pool and is admitted only after passing the domination check; none of the unconditional guarantees depend on it.
4. Lifted candidate $C_L = F \cup \ell(D_R)$: lifts the reduced solution back to original labels.
5. Original-graph linear candidates (all computed in $\mathcal{O}(n+m)$):
   • $C_G$ — greedy maximum-coverage (certifies the $H(\Delta+1)$ ratio)
   • $C_D$ — closed-degree coverage sweep
   • $C_W$, $C_M$ — low- and medium-degree witness sweeps
   • $C_O$ — order-ownership candidates (early and late)
   • $C_S$ — seed-and-complete
   • $C_B$ — Salvador-style bipartite auxiliary
   • $C_X$ — max-cut double-cover (min-side maximum cut of the bipartite double cover $B(H)$, decoded by first coordinate; validated)
   • $C_R$ — reverse-delete (multiple deterministic orders)
6. Pruning (PruneRedundantDominating): each candidate is made inclusion-minimal.
7. Portfolio minimum: the smallest valid (dominates the original graph) pruned candidate is returned.

Unconditional guarantees

• Feasibility (Theorem): every normal return is a dominating set of the input graph.
• Approximation ratio (Theorem): because the portfolio contains $C_G$, every returned set $D$ satisfies $|D| \le H(\Delta+1),\gamma(G) \le (1+\ln(\Delta+1)),\gamma(G) = \mathcal{O}(\log \Delta)$.
• Constant factor on bounded-degree graphs (Corollary): for any fixed $\Delta$, the ratio is at most $1 + \ln(\Delta+1)$.

Near-threshold ratio hypothesis

Furones is conjectured to satisfy $|D| \le \max\{4,,\frac{1}{2}\ln n\}\cdot\gamma(G)$ on every graph. Proving this for all graphs would imply P = NP (via Dinur–Steurer). The hypothesis is already proved unconditionally for all graphs of maximum degree $\Delta \le \sqrt{n}/e$.

Runtime

$\mathcal{O}(n+m)$ for fixed parameters (large hidden constant). The Baker reduced-solve uses the default $\varepsilon = 1$ (shift $k = 1$), a constant factor; the max-cut double-cover candidate $C_X$ is also $\mathcal{O}(n+m)$ (build the double cover with $2n$ nodes and $2m$ edges, then one BFS min-side cut).

CAR Benchmarks

The car/ folder contains three reproducible exact-optimum studies. Every study imports the installed Furones package and compares it against the exact domination number $\gamma(G)$ computed by exhaustive search.

CAR-001: Core Exact Benchmark (run_integrity_measurements.py)

• 1 000 instances, at most 14 vertices, seven graph families (Erdős–Rényi sparse/medium/dense, random bipartite, random trees, perturbed paths/cycles, small structured).
• Exact $\gamma(G)$ by exhaustive search for every instance.
• Result: Furones is optimal on all 1 000 instances (100.0 %); observed ratio $\hat{\rho} = 1.000$.

CAR-002: Per-Strategy Ablation (run_integrity_measurements.py)

Each exposed strategy is measured independently on the same 1 000-instance benchmark.

No single strategy is universally optimal; the portfolio minimum combines them to achieve 100 % optimal on every instance.

CAR-003: High-Degree / Dense Regime (run_high_degree_experiment.py)

Probes the regime $\Delta > \sqrt{n}/e$ left open by the low-degree proposition. Base seed 12 345, 1 000 instances from seven dense families (complete, cocktail-party, dense circulant, random regular, dense Erdős–Rényi, perturbed hypercube, perturbed Paley), including perfect-code stress cases ($\tau(G) = 1$).

Furones is optimal on all 1 000 high-degree instances, including every $\tau(G) = 1$ perfect-code case. Zero violations of $\rho(n) = \max\{4, \frac{1}{2}\ln n\}$.

CAR-004: Adversarial Stress Test (run_adversarial_experiment.py)

Actively searches for worst-case instances. Base seed 1 000, 10 000 instances from seven adversarial families: greedy traps, geometric set-cover gadgets, perturbed perfect-code graphs, near-efficient circulants, cocktail-party/multipartite graphs, dense random-regular, and dense Erdős–Rényi. Exact $\gamma(G)$ by exhaustive search on every instance.

Zero violations of $\rho(n)$ across all 10 000 adversarial instances. The worst observed ratio was 1.333 (a dense random-regular graph, $n = 16$, $\gamma = 3$, returned size 4), well below $\rho = 4$.

Problem Statement

Input: A Boolean Adjacency Matrix $M$.

Answer: Find a Minimum Dominating Set.

Example Instance: 5 × 5 matrix

The input for undirected graphs is provided in DIMACS format:

p edge 5 4
e 1 3
e 1 5
e 2 4
e 3 5

Example Solution:

Dominating Set Found 1, 2: nodes 1 and 2 constitute an optimal solution.

Compile and Environment

Prerequisites

• Python ≥ 3.12

Installation

pip install furones

Execution

1. Clone the repository:

   git clone https://github.com/frankvegadelgado/furones.git
   cd furones
   

2. Run the script:

   asia -i ./benchmarks/testMatrix1
   

   Example Output:

   testMatrix1: Dominating Set Found 1, 2
   

Dominating Set Size

Use the -c flag to count the nodes in the Dominating Set:

asia -i ./benchmarks/testMatrix2 -c

Output:

testMatrix2: Dominating Set Size 4

Command Options

asia -h

Output:

usage: asia [-h] -i INPUTFILE [-a] [-b] [-c] [-v] [-l] [--consistency] [--version]

Solve the Approximate Minimum Dominating Set for undirected graph encoded in DIMACS format.

options:
  -h, --help            show this help message and exit
  -i INPUTFILE, --inputFile INPUTFILE
                        input file path
  -a, --approximation   enable comparison with a polynomial-time approximation approach within a logarithmic factor
  -b, --bruteForce      enable comparison with the exponential-time brute-force approach
  -c, --count           calculate the size of the Dominating Set
  -v, --verbose         enable verbose output
  -l, --log             enable file logging
  --consistency         require a linear-time certificate for the Furones approximation bound
  --version             show program's version number and exit

Batch Execution

batch_asia -h

Output:

usage: batch_asia [-h] -i INPUTDIRECTORY [-a] [-b] [-c] [-v] [-l] [--consistency] [--version]

Solve the Approximate Minimum Dominating Set for all undirected graphs encoded in DIMACS format and stored in a directory.

options:
  -h, --help            show this help message and exit
  -i INPUTDIRECTORY, --inputDirectory INPUTDIRECTORY
                        Input directory path
  -a, --approximation   enable comparison with a polynomial-time approximation approach within a logarithmic factor
  -b, --bruteForce      enable comparison with the exponential-time brute-force approach
  -c, --count           calculate the size of the Dominating Set
  -v, --verbose         enable verbose output
  -l, --log             enable file logging
  --consistency         require a linear-time certificate for the Furones approximation bound
  --version             show program's version number and exit

Testing Application

usage: test_asia [-h] -d DIMENSION [-n NUM_TESTS] [-s SPARSITY] [-a] [-b] [-c] [-w] [-v] [-l] [--consistency] [--version]

The Furones Testing Application using randomly generated, large sparse matrices.

options:
  -h, --help            show this help message and exit
  -d DIMENSION, --dimension DIMENSION
                        an integer specifying the dimensions of the square matrices
  -n NUM_TESTS, --num_tests NUM_TESTS
                        an integer specifying the number of tests to run
  -s SPARSITY, --sparsity SPARSITY
                        sparsity of the matrices (0.0 for dense, close to 1.0 for very sparse)
  -a, --approximation   enable comparison with a polynomial-time approximation approach within a logarithmic factor
  -b, --bruteForce      enable comparison with the exponential-time brute-force approach
  -c, --count           calculate the size of the Dominating Set
  -w, --write           write the generated random matrix to a file in the current directory
  -v, --verbose         enable verbose output
  -l, --log             enable file logging
  --consistency         require a linear-time certificate for the Furones approximation bound
  --version             show program's version number and exit

Code

• Python implementation by Frank Vega.

Complexity

+ We present a linear-time portfolio algorithm for MDS with an unconditional H(Δ+1) approximation guarantee and exact performance across the CAR benchmarks: optimal on all 1 000 core and 1 000 high-degree instances, and zero factor-4 violations across 10 000 adversarial instances.

License

• MIT License.