[Model] MinimumGeometricConnectedDominatingSet

[isPANN]

Motivation

GEOMETRIC CONNECTED DOMINATING SET (P124) from Garey & Johnson, A2 ND48. Find the minimum connected dominating set in a set of points under a distance threshold. NP-complete via reduction from PLANAR 3SAT (Lichtenstein, 1982). Applications in wireless ad-hoc network backbone construction.

Associated rules:

• [Rule] PLANAR 3SAT to MinimumGeometricConnectedDominatingSet #377: Planar3Satisfiability → MinimumGeometricConnectedDominatingSet (NP-completeness proof)

Definition

Name: MinimumGeometricConnectedDominatingSet

Reference: Garey & Johnson, Computers and Intractability, A2 ND48

Mathematical definition:

INSTANCE: Set P ⊆ Z×Z of points in the plane, positive integer B.
OBJECTIVE: Find the minimum-size subset P' ⊆ P such that all points in P − P' are within Euclidean distance B of some point in P', and the graph G = (P', E) with edges between points within distance B is connected.

Variables

• Count: |P| (one binary variable per point)
• Per-variable domain: {0, 1}
• Meaning: Whether each point is selected into the dominating subset P'. A valid solution requires domination (every non-member has a neighbor in P') and connectivity (the subgraph on P' is connected). The objective minimizes |P'|.

Schema (data type)

Type name: MinimumGeometricConnectedDominatingSet
Variants: none

Field	Type	Description
points	Vec<(f64, f64)>	Set of points P in the plane
radius	f64	Distance threshold B

Notes:

• This is an optimization problem: Value = Min<usize>.
• Key getter methods: num_points() (= |P|), radius().
• Equivalent to Minimum Connected Dominating Set on the unit disk graph (UDG) induced by the point set.

Complexity

• Decision complexity: NP-complete (Lichtenstein, 1982; transformation from PLANAR 3SAT). NP-complete under L_1 and L_∞ metrics as well.
• Best known exact algorithm: O*(1.9407^n) via Measure and Conquer for connected dominating set (Fomin, Grandoni, Kratsch, 2006).
• Concrete complexity expression: "2^num_points" (for declare_variants!)
• Approximation: PTAS on unit disk graphs. Constant-factor approximation for weighted version (Ambühl et al., 2006).
• References:
  • D. Lichtenstein (1982). "Planar Formulae and Their Uses." SIAM J. Comput. 11(2), pp. 329-343.
  • F.V. Fomin, F. Grandoni, D. Kratsch (2006). "Solving Connected Dominating Set Faster than 2^n." FSTTCS 2006, LNCS 4337, pp. 152-163.

Extra Remark

Full book text:

INSTANCE: Set P ⊆ Z×Z of points in the plane, positive integers B and K.
QUESTION: Is there a subset P' ⊆ P with |P'| ≤ K such that all points in P − P' are within Euclidean distance B of some point in P', and such that the graph G = (P',E), with an edge between two points in P' if and only if they are within distance B of each other, is connected?
Reference: [Lichtenstein, 1977]. Transformation from PLANAR 3SAT.
Comment: Remains NP-complete if the Euclidean metric is replaced by the L_1 rectilinear metric or the L_∞ metric [Garey and Johnson, ——].

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all 2^|P| subsets; check domination and connectivity; return smallest.)
• It can be solved by reducing to integer programming. (Binary variable per point; domination and flow-based connectivity constraints; minimize Σ x_i. Companion rule issue to be filed separately.)
• Other: Branch-and-bound with Measure and Conquer.

Example Instance

Input:
P = {(0,0), (3,0), (6,0), (9,0), (0,3), (3,3), (6,3), (9,3)} (8 points), B = 3.5

The induced graph is a ladder: horizontal edges between consecutive points in each row (dist=3.0 ≤ 3.5), plus vertical edges between corresponding points in the two rows (dist=3.0 ≤ 3.5). No diagonal edges (dist = √18 ≈ 4.24 > 3.5).

Optimal CDS (size 4): P' = {(0,0), (3,0), (6,0), (9,0)} (entire bottom row)

• Connectivity: (0,0)-(3,0)-(6,0)-(9,0) forms a path ✓
• Domination: (0,3) is within dist 3.0 of (0,0) ✓, (3,3) within 3.0 of (3,0) ✓, (6,3) within 3.0 of (6,0) ✓, (9,3) within 3.0 of (9,0) ✓

Optimal value: Min(4) — 7 valid CDS of size 4 exist. No size-3 CDS exists (verified exhaustively: any 3-point subset either fails connectivity or leaves some point undominated).

Python validation script

import math
from itertools import combinations

points = [(0,0),(3,0),(6,0),(9,0),(0,3),(3,3),(6,3),(9,3)]
B = 3.5

def dist(p1, p2):
    return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)

n = len(points)
adj = [[dist(points[i],points[j]) <= B and i != j for j in range(n)] for i in range(n)]

def is_cds(subset):
    s = set(subset)
    # Domination
    for i in range(n):
        if i not in s and not any(adj[i][j] for j in s):
            return False
    # Connectivity
    visited = {subset[0]}
    q = [subset[0]]
    while q:
        node = q.pop(0)
        for nb in s:
            if nb not in visited and adj[node][nb]:
                visited.add(nb); q.append(nb)
    return visited == s

for k in range(1, n+1):
    found = [c for c in combinations(range(n), k) if is_cds(list(c))]
    if found:
        assert k == 4
        print(f"Min CDS: {k} ({len(found)} solutions)")
        break

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	No planned reduction rules connecting to the existing graph
Non-trivial	✅ Pass	Distinct feasibility constraints from existing problems
Correctness	⚠️ Warn	Complexity bound is outdated; example instance is incorrect
Well-written	❌ Fail	ILP companion issue not linked; example has wrong expected outcome

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

The problem GeometricConnectedDominatingSet does not yet exist in the codebase (pred show confirms). The closest existing problems are MinimumDominatingSet (graph-based, no connectivity requirement) and MaximumIndependentSet/UnitDiskGraph (different objective entirely), so it is a novel addition.

However, the issue body does not mention any concrete reduction rule connecting this problem to the existing reduction graph. There is no "reduces to/from X" statement, no crossref to a planned [Rule] issue, and no explicit connection beyond the generic ILP solvability claim. A problem without any planned reduction rule risks being an orphan node in the graph.

Verdict: Warn — please add at least one planned reduction (e.g., from ConnectedDominatingSet on general graphs, or to/from MinimumDominatingSet, or a specific reduction from 3-SAT/Planar-3-SAT).

Non-trivial

Pass. The problem has genuinely different feasibility constraints from all existing problems in the codebase:

• Unlike MinimumDominatingSet, it requires the selected subset to induce a connected subgraph.
• Unlike graph-based domination problems, the graph is implicitly defined by Euclidean distances between points in the plane.
• The combination of geometric structure + domination + connectivity is distinct from any existing model.

Correctness

Reference verification:

1. Lichtenstein (1982), "Planar Formulae and Their Uses", SIAM J. Comput. 11(2), pp. 329-343 — Verified. The paper exists and does prove NP-completeness of Geometric Connected Dominating Set via transformation from Planar 3-SAT. The claim in the issue is correct.

2. Fomin, Grandoni, Kratsch (2006), "Solving Connected Dominating Set Faster than 2^n", FSTTCS 2006 — Verified. The paper exists and presents an O*(1.9407^n) algorithm. However, the issue claims this is the best known exact algorithm, which is outdated. Subsequent work has improved the bound:

   • O*(1.8966^n) via improved Measure and Conquer analysis
   • O*(1.8619^n) by Abu-Khzam and Mouawad (2010), "An exact algorithm for connected red-blue dominating set", published in J. Discrete Algorithms 9(3), 2011

3. Ambuehl et al. (2006), "Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs", APPROX 2006 — Verified. The paper exists and the approximation claim is correct.

Example instance verification (critical error):

The example claims K=4 and presents P' = {(1,0), (2,0), (1,1), (2,1)} as the solution, stating that "Selecting only 3 points fails to dominate (3,2)." This is incorrect. Brute-force enumeration reveals:

• Minimum CDS has size 2: P' = {(1,1), (2,1)} is a valid connected dominating set — every other point is within distance 1.5 of one of these two points, and the two points are adjacent (distance 1.0).
• There are 8 valid CDS of size 3 (e.g., {(1,0), (1,1), (2,1)}, {(3,0), (1,1), (2,1)}, etc.)
• There are 35 valid CDS of size ≤ 4.

The example with K=4 is trivially satisfiable (the minimum is 2), making it useless for round-trip testing. A correct example should use K=2 (the actual minimum) or restructure the point set so the problem is more constrained.

Verdict: Warn — the references exist but the complexity bound is outdated, and the example solution/analysis is factually wrong.

Recommendations

• Update the best known exact algorithm to O*(1.8619^n) by Abu-Khzam and Mouawad (2010/2011).
• Fix the example instance: either use a point configuration where the minimum CDS is larger, or set K to the actual minimum (K=2) and discuss why smaller subsets fail.

Well-written

4a: Information Completeness

Section	Status
Motivation	✅ Present
Name	✅ Valid
Reference	✅ Present (Garey & Johnson, Lichtenstein)
Definition	✅ Clear INSTANCE/QUESTION format
Variables	✅ Present
Schema	✅ Present with field table
Complexity	⚠️ Present but outdated bound
How to solve	❌ ILP claimed but no companion [Rule] GeometricConnectedDominatingSet to ILP issue linked
Example Instance	❌ Present but factually incorrect (see Correctness)
Expected Outcome	❌ Claims K=4 is needed when minimum is 2

4b: Definition Completeness — Pass. The formal definition is precise and implementable with clear INSTANCE/QUESTION format.

4c: Symbol and Notation Consistency — Pass. Symbols (P, P', B, K, G, E) are consistent across sections.

4d: Example Quality — Fail. The example is factually incorrect:

• Claims "Selecting only 3 points fails to dominate (3,2)" but {(1,1), (2,1)} alone dominates all points.
• With K=4 and minimum CDS size 2, there are 35 feasible solutions — the example is trivially satisfiable and cannot catch implementation bugs.
• A round-trip test with this instance would pass even with a broken reduction.

4e: Representation Feasibility — Pass. The schema uses Vec<(f64, f64)> for points, f64 for radius, and usize for bound, which is appropriate.

Fail items:

1. ILP is checked in "How to solve" but no companion [Rule] GeometricConnectedDominatingSet to ILP issue is linked or referenced.
2. Example instance is incorrect — the claimed solution of size 4 is far from optimal (minimum is 2), and the stated reasoning about why size 3 fails is wrong.

Recommendations

• Link or create a [Rule] GeometricConnectedDominatingSet to ILP issue if direct ILP solvability is claimed.
• Redesign the example: use a point configuration where the minimum CDS is at least 3-4, with K set to the actual minimum, so the example has discriminative power for testing.
• Consider whether the problem should be named MinimumConnectedDominatingSet (optimization) rather than GeometricConnectedDominatingSet (decision), since the codebase convention uses optimization prefixes. However, the G&J name uses the decision formulation, so either convention could be justified.

[isPANN]

Renamed from GeometricConnectedDominatingSet to MinimumGeometricConnectedDominatingSet. Converted from decision framing (bound K) to optimization framing (minimize dominating set size). Removed bound field from schema. Changed Value type from Or to Min<usize>. Removed PoorWritten label.

[isPANN]

Fix-issue changelog

• Example (Correctness fix): Replaced wrong example — old instance claimed Min(4) but actual minimum was 2 ({(1,1),(2,1)}). New example uses 8-point ladder graph (two rows of 4, spacing 3, B=3.5) with verified Min(4), 7 solutions, no 3-CDS.
• Associated rules: Linked [Rule] PLANAR 3SAT to MinimumGeometricConnectedDominatingSet #377 (Planar3SAT → MinimumGeometricConnectedDominatingSet).
• Complexity: Added concrete expression "2^num_points".
• Schema notes: Added Value = Min<usize> and getter methods.
• ILP: Added companion rule note.
• Added Python validation script.

Applied by /fix-issue.