The Furones Algorithm

An Approximation Algorithm for Minimum Dominating Set via Planar Kernel Reduction

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 the best known polynomial-time approximation factor is $O(\ln n)$ , which is provably tight unless $\mathrm{P}=\mathrm{NP}$ . We present the current Furones v0.2.8 implementation, which reduces an arbitrary undirected graph to a planar kernel through forced-vertex extraction, pendant elimination with selective removal, and a linear-time forest projection. Baker's PTAS is then applied to the planar kernel. The non-PTAS part of the algorithm runs in $O(n+m)$ worst-case time, and the full algorithm is linear whenever Baker's fixed-parameter planar subroutine is implemented in linear time.

The algorithm always returns a valid dominating set. It is provably a 2-approximation whenever the reduction is tight, and the command-line flag --consistency enables a linear-time sufficient certificate for the currently proved 2-approximation cases. This certificate is deliberately conservative: it accepts the tight case and the proved full forced-boundary condition, but it does not claim a universal 2-approximation for general graphs. The experiments use Furones v0.2.8 with --consistency on 68 NPBench DIMACS clique-complement instances and on a 64-graph compendium selected from Cai's VC-Bench collection, where the second experiment also compares against NetworkX 3.4.2's logarithmic approximation.

---

Introduction

The Minimum Dominating Set 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 hardness result implies that no polynomial-time algorithm can approximate set cover, and therefore dominating set, within $(1-\varepsilon)\ln n$ for every fixed $\varepsilon>0$ unless $\mathrm{P}=\mathrm{NP}$ . Consequently, any polynomial-time universal constant-factor guarantee such as 2 would imply $\mathrm{P}=\mathrm{NP}$ .

The current Furones algorithm should be read with this barrier in mind. It gives a valid dominating set for every input, a proved 2-approximation in tight reductions, and a linear-time --consistency mode that refuses to certify instances outside the currently proved sufficient conditions.

---

Current Algorithm

The implementation is in furones/algorithm.py, with the reduction in furones/tscc_ds_reduction.py and Baker's planar routine in furones/baker_algo.py.

At a high level, find_dominating_set(graph, eps=1, consistency=False) performs five phases:

1. Preprocessing. Remove self-loops and separate isolated vertices. Isolated vertices must be included in every dominating set.
2. Cascade reduction. Apply the dominating-set isolated and pendant rules until the working graph has minimum degree at least 2.
3. Linear forest projection. If the residual is non-planar, replace it by a DFS spanning forest projection and run the cascade again. The projection is planar by construction and is built in linear time.
4. Planar-kernel approximation. Apply Baker's PTAS to the planar kernel. With $\varepsilon=1$ , the planar subroutine is used at factor 2.
5. Lifting and pruning. Lift the kernel solution with the forced vertices, then greedily remove redundant vertices while preserving domination.

The current algorithm.py also contains the linear-time sufficient certificate used by --consistency:

class ApproximationNotCertifiedError(RuntimeError):
    """Raised when linear-time consistency checks cannot certify a 2-bound."""


def is_two_approximation_certified(
    graph: nx.Graph,
    reduced_graph: nx.Graph,
    forced_ds: Set,
    dominating_set: Set,
) -> bool:
    """
    Linear-time sufficient check for the proved 2-approximation cases.

    The certificate is intentionally conservative. It accepts the tight case
    and the non-tight case covered by the proved inequality |F| >= 2|F_R|.
    It does not use the post-pruning boundary alone, and it does not
    claim a universal 2-approximation for general graphs.
    """
    if not nx.is_dominating_set(graph, dominating_set):
        return False

    reduced_nodes = set(reduced_graph.nodes())
    forced_boundary = {
        v for v in reduced_nodes
        if any(u in forced_ds for u in graph.neighbors(v))
    }
    return not forced_boundary or len(forced_ds) >= 2 * len(forced_boundary)

The main routine calls the certificate only after building and verifying a dominating set:

def find_dominating_set(graph, eps=1, consistency=False):
    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.")

    if graph.number_of_nodes() == 0:
        return set()
    if graph.number_of_edges() == 0:
        return set(graph.nodes())

    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

    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.")

    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

    approximate_dominating_set = prune_redundant_vertices_dominating(
        working_graph, D
    )
    approximate_dominating_set.update(isolates)

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

    if consistency:
        certified = is_two_approximation_certified(
            working_graph,
            G_reduced,
            forced_ds,
            approximate_dominating_set - isolates,
        )
        if not certified:
            raise ApproximationNotCertifiedError(
                "Linear-time consistency checks cannot certify a 2-approximation "
                "for this instance. A universal polynomial 2-approximation for "
                "general Dominating Set would imply P = NP.",
                approximate_dominating_set,
            )

    return approximate_dominating_set

---

Reduction Rules

Let $H$ be the current working graph and $F$ the forced set.

Rule 0 (isolated vertex). If $\deg_H(v)=0$ and $v$ is not already dominated by a forced neighbour in the original graph, add $v$ to $F$ and remove it. If it is already dominated by $F$ , remove it silently.

Rule 1 (pendant vertex). If $\deg_H(v)=1$ with unique $H$ -neighbour $u$ , then an optimum dominating set can be chosen to contain $u$ . Force $u$ , remove $u$ and $v$ , and remove only those neighbours of $u$ whose $H$ -neighbours all lie in $N_H[u]$ . Neighbours with outside connections are kept so they can still dominate the rest of the graph.

The key implementation change from older versions is the replacement of greedy planarization by a linear forest projection. If the cascade leaves a non-planar residual, tscc_ds_reduction.py builds a DFS spanning forest subgraph, discards cycle-closing edges, and re-runs the cascade. The forest is planar by construction, and the lift remains valid because every kept edge is an original edge.

---

Approximation Analysis

Let $G$ be the input graph, $F$ the forced set, $R=V(G_{\text{red}})$ the residual planar kernel, and $D$ the final pruned output. Define the forced-boundary set

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

When $F_R=\emptyset$ , the reduction is tight. In that case the forced vertices do not touch the residual kernel, and the planar-kernel approximation lifts cleanly:

$$|D|\le 2\gamma(G).$$

For the general non-tight case, the proved full-boundary sufficient condition is:

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

Therefore the current consistency certificate accepts whenever

$$F_R=\emptyset \quad\text{or}\quad |F|\ge 2|F_R|.$$

The pruning step motivates studying the post-pruning boundary

$$F_R^{\text{pruned}}=F_R\cap D,$$

but the implementation does not use $F_R^{\text{pruned}}$ alone as a universal certificate. A failed --consistency run means only that the sufficient proof condition did not fire; it does not mean that the returned dominating set is poor.

---

Runtime Analysis

Let $n=|V|$ and $m=|E|$ . The non-PTAS part of the current implementation runs in:

$$O(n+m).$$

The components are:

• Preprocessing and isolated-vertex handling: $O(n+m)$ .
• First cascade: $O(n+m)$ ; every vertex is queued a bounded number of times and each edge is inspected a bounded number of times.
• Forest projection: $O(n+m)$ ; a DFS spanning forest is planar by construction and avoids repeated planarity checks.
• Second cascade, if needed: $O(n+m)$ .
• Lifting, pruning, and domination verification: $O(n+m)$ .
• --consistency certificate: $O(n+m)$ , because it verifies domination and scans the reduced vertices and their adjacency.

Thus the full running time is:

$$O(n+m)+T_{\text{Baker}}(G_{\text{red}},\varepsilon).$$

For fixed $\varepsilon$ , a linear-time implementation of Baker's planar subroutine gives an overall linear-time algorithm. The current Python implementation uses the project Baker routine in baker_algo.py; the important change relative to older Furones versions is that the non-planar reduction no longer has the old $O(mn+m\log m)$ greedy planarization bottleneck.

---

Experiments

All experiments below use Furones v0.2.8 and the --consistency flag. The tables are derived from the logs stored in the Furones repository.

NPBench DIMACS clique-complement benchmark

The NPBench experiment uses DIMACS clique-complement instances from:

ThanhVu Nguyen and Thang Bui, NP-Complete Benchmark Instances, https://roars.dev/npbench/. The relevant repository path is the vertex-cover clique-complement folder.

Command:

python -m furones.batch -i .\experiments\ -c -l --consistency

Equivalent console script:

batch_asia -i .\experiments\ -c -l --consistency

The generated log was copied as experiments/np_bench.txt. Because every run completed with --consistency, all 68 returned solutions are certified by the implemented linear-time sufficient conditions.

Metric	Value
Instances	68
Certified by --consistency	68
Total algorithmic time	13.534 s
Median algorithmic time	85.799 ms
Maximum algorithmic time	1035.418 ms
Largest returned dominating set	172 on hamming10-2
Smallest returned dominating set	2 on c-fat and small Hamming instances
Slowest instance	brock800_4

Detailed rows from experiments/np_bench.txt:

Instance	n	m	D size	T_F ms	Consistency	Bound
brock200_1	200	5066	12	79.104	yes	<= 2
brock200_2	200	10024	7	69.520	yes	<= 2
brock200_3	200	7852	7	45.499	yes	<= 2
brock200_4	200	6811	9	41.027	yes	<= 2
brock400_1	400	20077	13	127.964	yes	<= 2
brock400_2	400	20014	13	141.828	yes	<= 2
brock400_3	400	20119	12	127.718	yes	<= 2
brock400_4	400	20035	13	96.426	yes	<= 2
brock800_1	800	112095	13	859.918	yes	<= 2
brock800_2	800	111434	12	653.505	yes	<= 2
brock800_3	800	112267	12	588.356	yes	<= 2
brock800_4	800	111957	12	1035.418	yes	<= 2
c-fat200-1	200	18366	2	76.947	yes	<= 2
c-fat200-2	200	16665	2	81.690	yes	<= 2
c-fat200-5	200	11427	2	60.935	yes	<= 2
c-fat500-1	500	120291	2	533.267	yes	<= 2
c-fat500-10	500	78123	2	379.581	yes	<= 2
c-fat500-2	500	115611	2	509.301	yes	<= 2
c-fat500-5	500	101559	2	706.302	yes	<= 2
C1000.9	1000	49421	36	275.494	yes	<= 2
C125.9	125	787	22	0.000	yes	<= 2
C250.9	250	3141	25	10.970	yes	<= 2
C500.9	500	12418	29	66.273	yes	<= 2
gen200_p0.9_44	200	1990	24	22.267	yes	<= 2
gen200_p0.9_55	200	1990	23	17.404	yes	<= 2
gen400_p0.9_55	400	7980	31	143.843	yes	<= 2
gen400_p0.9_65	400	7980	31	47.538	yes	<= 2
gen400_p0.9_75	400	7980	30	43.435	yes	<= 2
hamming10-2	1024	5120	172	38.668	yes	<= 2
hamming10-4	1024	89600	18	535.905	yes	<= 2
hamming6-2	64	192	15	0.000	yes	<= 2
hamming6-4	64	1312	2	15.273	yes	<= 2
hamming8-2	256	1024	48	9.930	yes	<= 2
hamming8-4	256	11776	6	70.361	yes	<= 2
johnson16-2-4	120	1680	8	7.148	yes	<= 2
johnson32-2-4	496	14880	16	64.438	yes	<= 2
johnson8-2-4	28	168	4	0.000	yes	<= 2
johnson8-4-4	70	560	8	0.000	yes	<= 2
keller4	171	5100	7	27.093	yes	<= 2
keller5	776	74710	16	413.935	yes	<= 2
MANN_a27	378	702	39	10.770	yes	<= 2
MANN_a45	1035	1980	66	47.806	yes	<= 2
MANN_a81	3321	6480	120	173.083	yes	<= 2
MANN_a9	45	72	14	12.538	yes	<= 2
p_hat1000-3	1000	127754	20	743.294	yes	<= 2
p_hat300-1	300	33917	4	147.821	yes	<= 2
p_hat300-2	300	22922	9	89.907	yes	<= 2
p_hat300-3	300	11460	16	55.926	yes	<= 2
p_hat500-1	500	93181	5	441.127	yes	<= 2
p_hat500-2	500	61804	12	300.894	yes	<= 2
p_hat500-3	500	30950	26	344.563	yes	<= 2
p_hat700-1	700	183651	4	906.348	yes	<= 2
p_hat700-2	700	122922	9	615.148	yes	<= 2
p_hat700-3	700	61640	22	320.006	yes	<= 2
san200_0.7_1	200	5970	9	30.371	yes	<= 2
san200_0.7_2	200	5970	8	255.688	yes	<= 2
san200_0.9_1	200	1990	20	13.806	yes	<= 2
san200_0.9_2	200	1990	21	10.775	yes	<= 2
san200_0.9_3	200	1990	22	15.211	yes	<= 2
san400_0.5_1	400	39900	6	190.746	yes	<= 2
san400_0.7_1	400	23940	10	109.924	yes	<= 2
san400_0.7_2	400	23940	11	106.871	yes	<= 2
san400_0.7_3	400	23940	10	114.503	yes	<= 2
san400_0.9_1	400	7980	30	44.115	yes	<= 2
sanr200_0.7	200	6032	11	98.955	yes	<= 2
sanr200_0.9	200	2037	23	9.569	yes	<= 2
sanr400_0.5	400	39816	7	191.481	yes	<= 2
sanr400_0.7	400	23931	13	108.915	yes	<= 2

VC-Bench compendium and NetworkX comparison

The second experiment uses a 64-graph compendium selected from Cai's VC-Bench collection:

Shaowei Cai, A Collection of Large Graphs for Vertex Cover Benchmarking, 2017, https://lcs.ios.ac.cn/~caisw/graphs.html.

Command:

python -m furones.batch -i .\network\ -c -a -l --consistency

Equivalent console script:

batch_asia -i .\network\ -c -a -l --consistency

The -a flag runs NetworkX 3.4.2's default logarithmic-ratio dominating-set approximation before Furones. The logged upper bound is:

$$\log_2(n)\cdot \frac{|D_{\text{Furones}}|}{|D_{\text{NetworkX}}|}.$$

NetworkX's approximation is the standard logarithmic-ratio algorithm described in Vazirani, Approximation Algorithms, Springer, 2001.

Summary from network/network.txt:

Metric	Furones v0.2.8	NetworkX approximation
Instances solved	64	64
Total algorithmic time	9.827 s	461.644 s
Mean time	153.552 ms	7213.192 ms
Median time	11.565 ms	6.615 ms
Maximum time	1411.469 ms	128617.267 ms
Total returned set size	24557	49110
Mean returned set size	383.703	767.344
Median returned set size	26.000	45.000
Furones no larger than NetworkX	62/64	-

Detailed per-instance rows:

Instance	D_F size	T_F ms	D_NX size	T_NX ms	UB	Certified
bio-celegans	35	21.829	241	79.567	1.281	yes
bio-diseasome	97	13.082	276	85.794	3.167	yes
bio-dmela	1481	435.197	2664	12764.554	7.145	yes
bio-yeast	356	31.494	463	333.162	8.081	yes
ca-CSphd	523	28.987	554	476.615	10.269	yes
ca-Erdos992	440	79.386	461	1363.359	11.754	yes
ca-GrQc	788	159.655	2218	4862.762	4.271	yes
ca-netscience	57	34.949	138	22.417	3.538	yes
ia-email-EU	755	670.716	820	16967.082	13.797	yes
ia-email-univ	233	116.958	604	457.616	3.914	yes
ia-enron-only	25	10.048	73	8.127	2.452	yes
ia-fb-messages	263	68.861	594	510.342	4.563	yes
ia-infect-dublin	64	17.877	241	74.469	2.305	yes
ia-infect-hyper	7	26.160	5	0.000	9.548	yes
ia-reality	81	79.358	81	286.423	12.733	yes
inf-power	1500	180.161	2263	5326.914	8.133	yes
rt-retweet	32	7.856	33	0.000	6.385	yes
rt-twitter-copen	199	0.505	236	100.225	8.071	yes
scc_enron-only	2	49.686	1	0.000	14.380	yes
scc_fb-forum	28	369.487	322	963.753	0.777	yes
scc_infect-hyper	1	46.864	1	0.000	6.820	yes
scc_retweet	156	469.269	562	1849.766	2.841	yes
scc_retweet-crawl	6079	508.851	8447	73413.115	10.123	yes
scc_rt_alwefaq	17	9.646	35	0.000	2.997	yes
scc_rt_assad	9	0.000	16	0.000	2.862	yes
scc_rt_bahrain	27	5.158	37	6.804	4.502	yes
scc_rt_barackobama	15	0.000	29	0.000	3.270	yes
scc_rt_damascus	11	3.064	15	0.842	3.731	yes
scc_rt_dash	12	2.242	15	0.534	3.963	yes
scc_rt_gmanews	12	4.640	45	6.426	1.887	yes
scc_rt_gop	6	0.000	6	0.000	3.700	yes
scc_rt_http	1	0.000	1	0.000	2.322	yes
scc_rt_israel	11	0.000	11	0.000	4.459	yes
scc_rt_justinbieber	7	0.000	26	0.000	1.603	no
scc_rt_ksa	8	0.000	12	0.000	2.928	yes
scc_rt_lebanon	5	0.000	5	0.000	3.322	yes
scc_rt_libya	10	0.000	12	0.000	3.962	yes
scc_rt_lolgop	14	25.584	104	37.097	1.089	yes
scc_rt_mittromney	36	0.000	42	0.000	5.719	yes
scc_rt_obama	4	1.006	4	0.000	3.000	yes
scc_rt_occupy	19	1.662	22	2.577	4.993	yes
scc_rt_occupywallstnyc	10	6.294	45	3.365	1.553	yes
scc_rt_oman	5	1.049	6	0.000	3.333	yes
scc_rt_onedirection	3	2.218	27	1.122	0.570	yes
scc_rt_p2	12	0.000	12	0.000	4.700	yes
scc_rt_qatif	4	0.000	5	0.000	3.046	yes
scc_rt_saudi	7	2.041	17	1.019	1.979	yes
scc_rt_tcot	11	1.112	12	1.032	4.309	yes
scc_rt_tlot	6	0.000	6	0.000	3.700	yes
scc_rt_uae	7	1.039	8	1.021	3.649	yes
scc_rt_voteonedirection	3	0.000	3	0.000	2.807	yes
soc-dolphins	14	4.693	33	1.121	2.526	yes
soc-karate	4	2.231	8	0.000	2.544	yes
soc-wiki-Vote	214	127.561	415	204.852	5.051	yes
tech-as-caida2007	2401	687.418	3691	61090.660	9.557	yes
tech-routers-rf	490	127.025	805	875.531	6.723	yes
tech-WHOIS	682	671.057	2285	13022.264	3.841	yes
web-BerkStan	3067	588.120	5472	34108.009	7.615	yes
web-edu	249	267.021	1451	2493.434	1.985	yes
web-google	205	115.451	497	1262.731	4.266	yes
web-indochina-2004	1493	1411.469	7303	128617.267	2.754	yes
web-polblogs	108	83.663	246	297.053	4.096	yes
web-spam	859	1066.798	2346	25313.327	4.474	yes
web-webbase-2001	1277	1180.829	2682	74350.114	6.652	yes

The sole failed certificate is scc_rt_justinbieber, but the logged upper-bound ratio is $1.603<2$ . This illustrates that --consistency is a sufficient certificate, not an empirical-quality test.

---

Conclusion

The current Furones v0.2.8 implementation removes the old greedy-planarization bottleneck and makes the non-PTAS reduction linear time. It always returns a valid dominating set, proves a 2-approximation in tight reductions, and offers a conservative linear-time --consistency certificate for the proved non-tight cases. The NPBench clique-complement run certifies all 68 instances, and the VC-Bench comparison shows substantially smaller total returned dominating sets and much lower total algorithmic time than NetworkX's logarithmic approximation on the selected 64-graph compendium.