Frank Vega

Posted on Jun 27, 2025 • Edited on Apr 28

The Furones Algorithm

#algorithms #computerscience #programming #python

An Approximation Algorithm for Minimum Dominating Set via Planar Kernel Reduction

Frank Vega

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

vega.frank@gmail.com

Abstract

The Minimum Dominating Set problem is NP‑hard, and the best known polynomial‑time approximation factor is $O(\ln n)$ — proven optimal unless $\mathrm{P} = \mathrm{NP}$ . We present a polynomial‑time algorithm that reduces any input graph to a planar kernel via forced vertices, pendant elimination, and greedy planarization, then applies Baker’s PTAS, running in $O(mn + m\log m)$ time. The output is provably within twice the optimum whenever the reduction is tight, and we conjecture this extends universally. A universal 2‑approximation guarantee would contradict established inapproximability bounds, implying $\mathrm{P} = \mathrm{NP}$ . We discuss this theoretical consequence and provide an open‑source implementation, Furones v0.2.6.

Introduction

The Minimum Dominating Set (DS) problem is one of the fundamental NP‑hard problems in graph theory. Given an undirected graph $G = (V,E)$ , a set $D \subseteq V$ is a dominating set if every vertex $v \in V$ either belongs to $D$ or has a neighbour in $D$ . The goal is to find a dominating set of minimum cardinality, denoted $\gamma(G)$ .

The problem is notoriously hard to approximate. A simple greedy algorithm achieves an approximation factor of $O(\ln n)$ and this is essentially optimal: Feige proved that set cover (hence dominating set) cannot be approximated within $(1-\varepsilon)\ln n$ for any $\varepsilon>0$ unless $\mathrm{P} = \mathrm{NP}$ . Consequently, any polynomial‑time algorithm that guarantees a constant approximation ratio (e.g., 2) would imply $\mathrm{P} = \mathrm{NP}$ .

Despite this barrier, we present an algorithm that, surprisingly, appears to achieve a 2‑approximation universally. The algorithm, called find_dominating_set and implemented in the Furones package (v0.2.6), works as follows:

Preprocessing: remove self‑loops, handle isolated vertices (which must be in any dominating set).
Reduction to a planar kernel:
- Apply DS reduction rules (isolated vertex forces, pendant elimination with selective removal) to obtain a graph $H$ where every remaining vertex has degree $\ge 2$ .
- If $H$ is non‑planar, construct a planar spanning subgraph $P$ using a greedy edge‑selection strategy that respects planarity.
- Re‑apply the reduction rules on $P$ to obtain a final planar graph $G_{\text{red}}$ of minimum degree $\ge 2$ .
Approximate solution on the planar kernel: Because $G_{\text{red}}$ is planar, we run Baker’s PTAS with parameter $\varepsilon = 1$ (giving $k = \lceil 1/\varepsilon \rceil = 1$ ), which yields a 2‑approximation for the minimum dominating set on planar graphs.
Lifting: The solution on $G_{\text{red}}$ is combined with the forced vertices from the reduction to produce a dominating set of the original graph.
Pruning: Redundant vertices are greedily removed from the lifted solution while preserving feasibility.

The running time is $O(mn + m\log m)$ due to the greedy planarization step, which makes the algorithm particularly attractive for sparse graphs ( $m = O(n)$ ) where it runs in $O(n\log n)$ .

The main contributions of this paper are:

A practical dominating set algorithm with a provable 2‑approximation guarantee for tight reductions and a conjectured universal constant ratio.
A rigorous analysis showing a 2‑approximation guarantee for all graphs in which the reduction is tight (i.e., no forced vertex neighbours the residual planar kernel), together with an explicit bound for the general case.
A theoretical consequence: if the algorithm achieves a 2‑approximation universally, then $\mathrm{P} = \mathrm{NP}$ , because it would violate the known $(\ln n)$ hardness barrier.
An open‑source implementation (Furones v0.2.6).

Algorithm Description

The core algorithm is implemented in the Python module algorithm.py. The reduction to a planar kernel is implemented in tscc_ds_reduction.py, and Baker’s PTAS for planar graphs is implemented in baker_algo.py.

1. Main entry point (`algorithm.py`)

# Created on 26/07/2025
# Author: Frank Vega

import itertools

import networkx as nx
from . import tscc_ds_reduction
from . import baker_algo
from collections import defaultdict
from typing import Dict, Set

def prune_redundant_vertices_dominating(G: nx.Graph, D: Set) -> Set:
    """
    O(n + m).  Mirrors prune_redundant_vertices_dominating().

    v ∈ D is *redundant* (safely removable) iff:
      (a) dom_count[v] ≥ 1  — v has a D-neighbour → v stays dominated
      (b) ∀ u ∈ N(v):  u ∈ D  OR  dom_count[u] ≥ 2
          — every neighbour of u retains ≥ 1 D-neighbour after v leaves

    dom_count is updated immediately on each removal so later checks
    see the tighter, already-pruned state.
    """
    D = set(D)
    dom_count: Dict = defaultdict(int)
    for v in D:
        for u in G.neighbors(v):
            dom_count[u] += 1

    for v in list(D):
        # (a) v must remain dominated
        if dom_count[v] < 1:
            continue
        # (b) every neighbour of v must remain dominated
        if all(u in D or dom_count[u] >= 2 for u in G.neighbors(v)):
            D.discard(v)
            for u in G.neighbors(v):
                dom_count[u] -= 1

    return D

def find_dominating_set(graph, eps=1):
    """
    Compute an approximate minimum dominating set (MDS) of an undirected graph.

    The algorithm combines structural reductions with Baker's PTAS for planar graphs.
    Specifically, it reduces the input to a planar 2-connected core (TSCC form),
    applies a (1 + ε)-approximation scheme on the reduced instance, and lifts the
    solution back to the original graph.

    Guarantees:
        • For general graphs, the algorithm returns a valid dominating set.
        • If the reduced instance is planar, the solution achieves a
          (1 + ε)-approximation with respect to the reduced graph.
        • The overall approximation factor depends on the reduction and lifting
          steps and is typically small in practice.

    Args:
        graph (nx.Graph):
            An undirected NetworkX graph.
        eps (float):
            Approximation parameter ε ∈ (0, 1].

    Returns:
        set:
            A dominating set of the input graph.

    Raises:
        ValueError:
            If the input is invalid or ε ∉ (0, 1].
        RuntimeError:
            If a required structural assumption is violated.
    """

    # --- Parameter validation ---
    if eps <= 0 or eps > 1:
        raise ValueError("epsilon must be in this interval (0, 1].")
    if not isinstance(graph, nx.Graph):
        raise ValueError("Input must be an undirected NetworkX Graph.")

    # --- Trivial cases ---
    if graph.number_of_nodes() == 0 or graph.number_of_edges() == 0:
        return set()

    # --- Preprocessing ---
    working_graph = graph.copy()
    working_graph.remove_edges_from(list(nx.selfloop_edges(working_graph)))
    isolates = set(nx.isolates(working_graph))
    working_graph.remove_nodes_from(isolates)
    if working_graph.number_of_nodes() == 0:
        return isolates

    # --- Reduction phase ---
    G_reduced, forced_ds, lift = tscc_ds_reduction.reduce_to_tscc_for_ds(working_graph)
    if not nx.is_planar(G_reduced):
        raise RuntimeError("2-connected edge graph is not planar.")

    # --- PTAS phase (on reduced graph) ---
    if G_reduced:
        mapping = {u: k for k, u in enumerate(G_reduced.nodes())}
        unmapping = {k: u for u, k in mapping.items()}
        G = baker_algo.Graph(G_reduced.number_of_nodes())
        for u, v in G_reduced.edges():
            G.add_edge(mapping[u], mapping[v])
        ptas_sol = baker_algo.baker_ptas(G, eps, verbose=False)
        md_reduced = {unmapping[u] for u in ptas_sol}
        D = lift(md_reduced)
    else:
        D = forced_ds

    # --- Postprocessing ---
    approximate_dominating_set = prune_redundant_vertices_dominating(working_graph, D)
    approximate_dominating_set.update(isolates)

    # --- Verification ---
    if not nx.is_dominating_set(graph, approximate_dominating_set):
        raise RuntimeError("Invalid solution: the computed set is not a dominating set.")
    return approximate_dominating_set

def find_dominating_set_brute_force(graph):
    if graph.number_of_nodes() == 0 or graph.number_of_edges() == 0:
        return None
    n_vertices = len(graph.nodes())
    for k in range(1, n_vertices + 1):
        for candidate in itertools.combinations(graph.nodes(), k):
            dominating_candidate = set(candidate)
            if nx.dominating.is_dominating_set(graph, dominating_candidate):
                return dominating_candidate
    return None

def find_dominating_set_approximation(graph):
    if graph.number_of_nodes() == 0 or graph.number_of_edges() == 0:
        return None
    dominating_set = nx.approximation.min_weighted_dominating_set(graph)
    return dominating_set

2. Reduction to planar kernel (`tscc_ds_reduction.py`)

The reduction implements two rules:

Rule 0 (isolated vertex): If $\deg_H(v)=0$ and $v$ is not already dominated by a forced vertex, then add $v$ to forced set and remove it.
Rule 1 (pendant vertex): If $\deg_H(v)=1$ with unique neighbour $u$ and $v$ not already dominated, force $u$ , remove $u$ and $v$ , and also remove neighbours of $u$ that have no external neighbours (keep those with outside connections).

If the residual is non‑planar, we build a planar spanning subgraph greedily and re‑apply the cascade. The output $G_{\text{red}}$ is always planar.

2.1. Reduction to planar kernel (`tscc_ds_reduction.py`)

from __future__ import annotations
import networkx as nx
from collections import deque
from typing import Any, Callable, Dict, FrozenSet, Set, Tuple

def _run_cascade(H: nx.Graph, forced_ds: Set[Any], original_G: nx.Graph) -> None:
    q = deque(v for v in H if H.degree(v) <= 1)
    in_q = set(q)
    while q:
        v = q.popleft()
        if v not in H:
            continue
        dv = H.degree(v)
        if dv == 0:
            if any(nb in forced_ds for nb in original_G.neighbors(v)):
                H.remove_node(v)
            else:
                forced_ds.add(v)
                H.remove_node(v)
        elif dv == 1:
            u = next(iter(H.neighbors(v)))
            if any(nb in forced_ds for nb in original_G.neighbors(v) if nb != u):
                H.remove_node(v)
                if u in H and u not in in_q and H.degree(u) <= 1:
                    in_q.add(u)
                    q.append(u)
                continue
            neighbors_u = list(H.neighbors(u))
            closed_u = set(neighbors_u) | {u}
            kept = []
            to_remove = {u, v}
            for w in neighbors_u:
                if w == v:
                    continue
                if any(x not in closed_u for x in H.neighbors(w)):
                    kept.append(w)
                else:
                    to_remove.add(w)
            forced_ds.add(u)
            for node in to_remove:
                if node in H:
                    H.remove_node(node)
            for w in kept:
                if w in H and w not in in_q and H.degree(w) <= 1:
                    in_q.add(w)
                    q.append(w)

def _greedy_planar_subgraph(G: nx.Graph) -> nx.Graph:
    if nx.check_planarity(G)[0]:
        return G.copy()
    n = G.number_of_nodes()
    max_planar_edges = max(3 * n - 6, n - 1)
    P = nx.Graph()
    P.add_nodes_from(G.nodes(data=True))
    _parent = {v: v for v in G}
    _rank = {v: 0 for v in G}
    def _find(x):
        while _parent[x] != x:
            _parent[x] = _parent[_parent[x]]
            x = _parent[x]
        return x
    def _unite(x, y):
        rx, ry = _find(x), _find(y)
        if rx == ry:
            return False
        if _rank[rx] < _rank[ry]:
            rx, ry = ry, rx
        _parent[ry] = rx
        if _rank[rx] == _rank[ry]:
            _rank[rx] += 1
        return True
    edges_sorted = sorted(G.edges(), key=lambda e: -(G.degree(e[0]) + G.degree(e[1])))
    back_edges = []
    for u, v in edges_sorted:
        if P.number_of_edges() >= max_planar_edges:
            break
        if _unite(u, v):
            P.add_edge(u, v)
        else:
            back_edges.append((u, v))
    for u, v in back_edges:
        if P.number_of_edges() >= max_planar_edges:
            break
        P.add_edge(u, v)
        if not nx.check_planarity(P)[0]:
            P.remove_edge(u, v)
    return P

def reduce_to_tscc_for_ds(G: nx.Graph) -> Tuple[nx.Graph, Set[Any], Callable[[Set[Any]], Set[Any]]]:
    H = nx.Graph(G)
    H.remove_edges_from(list(nx.selfloop_edges(H)))
    forced_ds = set()
    _run_cascade(H, forced_ds, G)
    is_planar, _ = nx.check_planarity(H)
    if not is_planar:
        P = _greedy_planar_subgraph(H)
        _run_cascade(P, forced_ds, G)
        H = P
    G_reduced = H.copy()
    frozen_forced = frozenset(forced_ds)
    def lift(ds_reduced: Set[Any]) -> Set[Any]:
        return frozen_forced | set(ds_reduced)
    return G_reduced, set(forced_ds), lift

def is_dominating_set(G: nx.Graph, D: Set[Any]) -> bool:
    D = set(D)
    return all(
        v in D or any(u in D for u in G.neighbors(v))
        for v in G.nodes()
    )

def verify_reduction_ds(G: nx.Graph, G_reduced: nx.Graph, forced_ds: Set[Any], lift: Callable[[Set[Any]], Set[Any]], ds_reduced: Set[Any]) -> Dict[str, Any]:
    lifted = lift(ds_reduced)
    min_deg_ok = all(G_reduced.degree(v) >= 2 for v in G_reduced.nodes())
    reduced_nodes = set(G_reduced.nodes())
    no_bridge_forced = all(len(set(G.neighbors(u)) & reduced_nodes) == 0 for u in forced_ds)
    return {
        "min_degree_ok": min_deg_ok,
        "no_bridge_forced": no_bridge_forced,
        "ds_reduced_ok": is_dominating_set(G_reduced, ds_reduced),
        "lifted_ds_ok": is_dominating_set(G, lifted),
        "lifted_ds": lifted,
        "forced_count": len(forced_ds),
        "reduced_count": len(ds_reduced),
        "total_count": len(lifted),
    }

3. Baker’s PTAS (`baker_algo.py`)

For a planar graph, Baker’s PTAS with $k = \lceil 1/\varepsilon \rceil$ returns a $(1+\varepsilon)$ -approximation. We use $\varepsilon = 1$ , so $k=1$ and the ratio becomes $2$ . The implementation (full code in baker_algo.py) includes BFS layering, tree‑decomposition DP, and greedy repair.

Key guarantee:

|\text{DS}{\text{PTAS}}| \le (1+\varepsilon)\,\gamma(G{\text{red}}).

With $\varepsilon=1$ this is factor 2.

Correctness

Theorem 1 (Correctness). Algorithm find_dominating_set always returns a valid dominating set of the input graph $G$ .

Proof sketch. Isolated vertices are added explicitly. The cascade (Rules 0 and 1) ensures every removed vertex is either in forced set or adjacent to forced set. The planarization step only removes edges, so any domination in the planar kernel holds in the original graph. Baker’s PTAS returns a dominating set of the kernel, which lifts to a dominating set of $G$ when combined with forced vertices. Pruning only removes redundant vertices while preserving domination. Hence the output is a valid dominating set. ∎

Approximation Ratio and Consequences for P vs NP

Structural setup

Let $G$ be the input graph, $F = D_{\text{forced}}$ the forced vertices, and $R = V(G_{\text{red}})$ the vertices of the planar kernel. Define the forced‑boundary set

F_R = { v \in R \mid N_G(v) \cap F \neq \emptyset }.

If $F_R = \emptyset$ the reduction is tight; otherwise non‑tight.

Exchange argument

Proposition 1 (Optimality of forced vertices). There exists a minimum dominating set $D^{\ast}$ of $G$ with $F \subseteq D^{\ast}$ .

Proof. For isolated vertices (Rule 0) they must be in every dominating set. For a pendant $v$ with neighbour $u$ (Rule 1), if an optimal set contains $v$ instead of $u$ , replace $v$ by $u$ — the neighbourhood of $u$ contains that of $v$ , so the set remains dominating and size unchanged. Repeating yields an optimal set containing all forced vertices. ∎

Key inequalities

Lemma 1 (Reduction bounds).

(i)

\gamma(G) \le |F| + \gamma(G_{\text{red}}).

(ii)

\gamma(G_{\text{red}}) \le \gamma(G) - |F| + |F_R|.

(iii)

|D| \le 2\gamma(G) - |F| + 2|F_R|.

Proof.

(i) Any dominating set of $G_{\text{red}}$ together with $F$ dominates all vertices.

(ii) Take optimal $D^{\ast}$ containing $F$ (Proposition 1). Its restriction to $R$ dominates all vertices of $G_{\text{red}}$ except possibly those in $F_R$ . Add one neighbour per such vertex to get a dominating set of $G_{\text{red}}$ of size at most $\gamma(G)-|F|+|F_R|$ .

(iii) Baker’s PTAS with $\varepsilon=1$ gives $|D_{\text{red}}| \le 2\gamma(G_{\text{red}})$ . Lifting gives $|F| + 2\gamma(G_{\text{red}})$ ; substitute (ii). ∎

Tight case: guaranteed 2‑approximation

Theorem 2 (2‑approximation for tight reductions). If $F_R = \emptyset$ , then $|D| \le 2\,\gamma(G)$ .

Proof. When $F_R = \emptyset$ , from the optimal set containing $F$ we have $\gamma(G_{\text{red}}) = \gamma(G) - |F|$ . Plug into Lemma 1(iii): $|D| \le 2\gamma(G) - |F| \le 2\gamma(G)$ . ∎

Non‑tight case and pruning

When $F_R \neq \emptyset$ , Lemma 1(iii) gives $|D| \le 2\gamma(G) - |F| + 2|F_R|$ . However, the pruning step (prune_redundant_vertices_dominating) removes many boundary vertices that are already dominated by forced vertices. Let $F_R^{\text{pruned}} \subseteq F_R$ be those that survive pruning (i.e., genuinely needed). Then

|D| \le 2\gamma(G) - |F| + 2|F_R^{\text{pruned}}|.

If one could prove $|F| \ge 2|F_R^{\text{pruned}}|$ for all graphs, the algorithm would be a universal 2‑approximation. This remains open.

Implication for P vs NP

Theorem 3 (P vs NP implication). If Algorithm find_dominating_set with $\varepsilon=1$ guarantees $|D| \le 2\gamma(G)$ for every undirected graph $G$ , then $\mathrm{P} = \mathrm{NP}$ .

Proof. Feige (1998) proved that no polynomial‑time algorithm can approximate Minimum Dominating Set within a factor of $(1-\varepsilon)\ln n$ for any $\varepsilon>0$ unless $\mathrm{P} = \mathrm{NP}$ . A factor‑2 approximation is a fixed constant, and for sufficiently large $n$ we have $2 < (1-\varepsilon)\ln n$ . Thus a universal 2‑approximation would contradict the hardness result, forcing $\mathrm{P} = \mathrm{NP}$ . ∎

Whether the algorithm actually attains a universal 2‑approximation is an open question. Theorem 2 establishes it unconditionally for tight reductions.

Runtime Analysis

Theorem 4 (Time complexity). Algorithm find_dominating_set runs in $O(mn + m\log m)$ , where $n = |V|$ and $m = |E|$ .

Proof sketch.

Preprocessing and cascade: $O(n+m)$ .
Greedy planarisation: sorts edges ( $O(m\log m)$ ), uses Union-Find to bypass planarity checks for tree edges (saving $O(n^2)$ work), and tests at most $m - n + 1$ back edges with $O(n)$ planarity checks each; total $O(m\log m + (m-n)n) = O(mn + m\log m)$ .
Baker’s PTAS on planar kernel ( $k=1$ ): $O(n)$ .
Lifting and pruning: $O(n+m)$ . The planarisation step dominates. For sparse graphs ( $m = O(n)$ ) the bound collapses to $O(n\log n)$ , providing a significant improvement over the naïve $O(n^2)$ . ∎

Experimental Study

We evaluated Furones v0.2.6 on thirteen complement graphs from the DIMACS Second Implementation Challenge benchmark suite. These graphs range in size from $n = 125$ to $n = 3321$ and in average degree $m/n$ from about 1.86 (MANN family) up to around 50 (brock200_2). For each instance we computed:

The dominating set size $|D|$ returned by find_dominating_set.
A reference value $\gamma^{\ast}$ obtained by solving the standard 0/1 integer linear programming formulation with a 300‑second wall‑clock limit (entries marked with $\dagger$ indicate that the ILP hit the time limit, so the reported value is a best‑known upper bound).

All experiments were run on the same workstation; times include parsing.

Approximation ratios

Table 1 reports the results.

Instance	$n$	$m$	$m/n$	$\gamma^{\ast}$	$\lvert D \rvert$	$\lvert D \rvert / \gamma^{\ast}$	$T_{\text{F}}$ (s)	$T_{\text{ILP}}$ (s)
C125.9	125	787	6.30	13	16	1.231	1.30	3.33
C250.9	250	3141	12.56	16	22	1.375	15.09	300.18 $^\dagger$
brock200_2	200	10024	50.12	4	5	1.250	39.22	26.29
brock200_4	200	6811	34.06	5	9	1.800	23.79	27.38
gen200_p0.9_44	200	1990	9.95	15	21	1.400	10.46	300.17 $^\dagger$
gen200_p0.9_55	200	1990	9.95	15	21	1.400	9.82	300.10 $^\dagger$
gen400_p0.9_55	400	7980	19.95	18	24	1.333	71.58	300.16 $^\dagger$
gen400_p0.9_65	400	7980	19.95	19	24	1.263	83.21	300.16 $^\dagger$
gen400_p0.9_75	400	7980	19.95	18	28	1.556	63.57	300.12 $^\dagger$
keller4	171	5100	29.82	5	7	1.400	21.41	16.21
MANN_a27	378	702	1.86	27	39	1.444	1.52	0.06
MANN_a45	1035	1980	1.91	45	66	1.467	15.46	0.11
MANN_a81	3321	6480	1.95	81	120	1.481	166.07	0.23

Summary: min ratio = 1.231, mean = 1.415, median = 1.400, max = 1.800.

Every instance yields a ratio strictly below 2, with the largest observed ratio being 1.800 (brock200_4). The mean and median around 1.4 indicate that the algorithm consistently produces near‑optimal solutions on these benchmarks.

Running time analysis

The running times in Table 1 exhibit three regimes, classified by average degree $m/n$ :

Sparse ( $m/n < 5$ ): the MANN family. Here the ILP solver is extremely fast (≤ 0.23 s) because the graphs are highly structured and the LP relaxation is integral. Furones scales as $O(n\log n)$ (e.g., from 1.52 s for $n=378$ to 166.07 s for $n=3321$ , close to the predicted quasi‑quadratic growth).
Medium density ( $5 \le m/n < 20$ ): the C250.9, gen200, and gen400 families. The ILP solver times out at 300 s on all of them, while Furones finishes in 9.82–83.21 s and returns ratios between 1.26 and 1.56.
Dense ( $m/n \ge 20$ ): brock200_2, brock200_4, keller4. Here both methods are competitive in time (Furones 21.41–39.22 s, ILP 16.21–27.38 s), but Furones never exceeds the time limit.

The key practical advantage of Furones is its predictable polynomial runtime: it never times out, even on dense or highly symmetric graphs where ILP solvers often struggle. Conversely, on extremely sparse and highly structured instances (MANN) the ILP solver is much faster, so the two methods are complementary.

Conclusion

We have presented a polynomial‑time algorithm that reduces any graph to a planar kernel and then applies Baker’s PTAS to obtain a dominant set. The algorithm provably achieves a 2‑approximation when the reduction is tight, and pruning recovers much of the overcount in the non‑tight case. A universal 2‑approximation would imply $\mathrm{P} = \mathrm{NP}$ . The implementation is freely available as the Furones package (v0.2.6) on PyPI.

DEV Community

The Furones Algorithm

An Approximation Algorithm for Minimum Dominating Set via Planar Kernel Reduction

Abstract

Introduction