[Rule] PLANAR 3SAT to MinimumGeometricConnectedDominatingSet

[isPANN]

Source: PLANAR 3SAT (Planar3Satisfiability)
Target: MINIMUM GEOMETRIC CONNECTED DOMINATING SET (MinimumGeometricConnectedDominatingSet)
Motivation: Establishes NP-hardness of MINIMUM GEOMETRIC CONNECTED DOMINATING SET by reduction from PLANAR 3SAT. The reduction exploits the planarity of the variable-clause incidence graph to embed variable and clause gadgets as geometric point configurations, where the distance threshold enforces connectivity constraints that mirror satisfiability.
Reference: Garey & Johnson, Computers and Intractability, ND48, p.219 (related); geometric CDS hardness results from computational geometry literature.

GJ Source Entry

GEOMETRIC CONNECTED DOMINATING SET
INSTANCE: A set P of points in the plane, a distance threshold B > 0, a positive integer K.
QUESTION: Is there a subset S ⊆ P with |S| ≤ K such that (1) every point in P \ S is within distance B of some point in S, and (2) the subgraph induced by S in the disk graph (edges between points within distance B) is connected?

Reference: Related to GT2 (DOMINATING SET) with geometric structure.

Reduction Algorithm

Given a Planar3Satisfiability instance with n variables and m clauses (where the variable-clause incidence bipartite graph is planar), construct a MinimumGeometricConnectedDominatingSet instance as follows:

Embedding the planar incidence graph

Since the incidence graph is planar, embed it in the plane using a standard planar embedding algorithm. Place variables and clauses on a grid with sufficient spacing.

Variable gadgets

For each variable x_i, place two points on the coordinate grid:

• true point T_i at position (2i, 0)
• false point F_i at position (2i, 1)

The distance between T_i and F_i is 1. Set the distance threshold B = 2.5 so that T_i and F_i are within range of each other. Selecting T_i in the dominating set represents x_i = true; selecting F_i represents x_i = false.

Clause gadgets

For each clause C_j = (l_1 ∨ l_2 ∨ l_3), create a clause center point c_j positioned near the midpoint of its three literal endpoints. Add bridge points along paths connecting c_j to each literal's variable gadget point:

• If x_i appears positively in C_j: create bridge points from T_i toward c_j
• If ¬x_i appears in C_j: create bridge points from F_i toward c_j

Bridge points are spaced at distance ≤ B apart to maintain potential connectivity. The number of bridge points depends on the embedding distance.

Distance threshold

B = 2.5 (or a value calibrated to the grid spacing so that variable gadget points and their bridge chains form valid disk-graph connections).

Bound K

K is set so that a connected dominating set of size ≤ K exists iff the formula is satisfiable. The exact value depends on the number of bridge points and gadget structure.

Solution extraction

From a minimum connected dominating set S:

• α(x_i) = true if T_i ∈ S (or the true-side bridge chain is selected)
• α(x_i) = false if F_i ∈ S (or the false-side bridge chain is selected)

Correctness

• (Forward): A satisfying assignment selects the appropriate literal point per variable and connects clause gadgets through satisfied literal bridges. The planarity ensures no crossing conflicts.
• (Backward): A connected dominating set of size ≤ K must choose exactly one truth value per variable (selecting both would exceed the budget) and must connect each clause center through at least one satisfied literal's bridge chain.

Codex verification needed: The geometric separation hypotheses (that unsatisfied literal bridges cannot contribute to connectivity within the budget K) are not fully proved in the derivation. The exact bridge point placement and bound K formula require careful verification.

Size Overhead

Target metric (code name)	Expression
num_points	Depends on bridge points (no clean closed-form)
radius	2.5 (constant)

Note: The number of points depends on the planar embedding distances. A rough bound is O(n + m + total_bridge_points), where bridge points scale with the grid distances in the planar embedding.

Implementation Note

MinimumGeometricConnectedDominatingSet currently has 0 outgoing reductions (no ILP solver). A MinimumGeometricConnectedDominatingSet → ILP rule should be implemented alongside this rule:

• Binary variable x_p ∈ {0,1} per point (in dominating set or not)
• Domination: for each point p, x_p + Σ_{q: dist(p,q)≤B} x_q ≥ 1
• Connectivity: flow-based or subtour-elimination constraints on the selected points
• Objective: minimize Σ x_p (Value = Min)
• Overhead: num_vars = "num_points", constraints = O(num_points^2)

Codex verification needed: The geometric construction details (exact bridge point coordinates, bound K) need careful verification against the planar embedding.

Example

Source (Planar3Satisfiability):
n = 3 variables (x_1, x_2, x_3), m = 1 clause:

• C_1 = (x_1 ∨ ¬x_2 ∨ x_3)

The incidence graph (3 variable nodes + 1 clause node, 3 edges) is trivially planar.

Target (MinimumGeometricConnectedDominatingSet):

Variable gadget points:

• x_1: T_1 = (0, 0), F_1 = (0, 1)
• x_2: T_2 = (2, 0), F_2 = (2, 1)
• x_3: T_3 = (4, 0), F_3 = (4, 1)

Clause center:

• c_1 = (2, 3) (positioned above the variable row)

Bridge points (connecting literals to clause center):

• x_1 positive bridge: b_{1,1} = (1, 1.5), b_{1,2} = (1.5, 2.25) (chain from T_1 toward c_1)
• ¬x_2 bridge: b_{2,1} = (2, 2) (chain from F_2 toward c_1)
• x_3 positive bridge: b_{3,1} = (3, 1.5), b_{3,2} = (2.5, 2.25) (chain from T_3 toward c_1)

Distance threshold B = 2.5.

Total points: 6 (variable) + 1 (clause center) + 5 (bridge) = 12 points.

Satisfying assignment: x_1=1, x_2=0, x_3=1

• C_1: x_1=T ✓
• Selected points: T_1, F_2, T_3, plus bridge points connecting through x_1's bridge to c_1. The connected dominating set covers all points within distance B.

Non-satisfying assignment: x_1=0, x_2=1, x_3=0

• C_1: (F ∨ F ∨ F) = F ✗
• No bridge from a selected literal point reaches c_1, so the dominating set cannot be connected within the budget.

Validation Method

• Closed-loop test: reduce Planar3Satisfiability to MinimumGeometricConnectedDominatingSet, solve target via ILP, extract truth assignment from selected points, verify all clauses satisfied
• Test with both satisfiable and unsatisfiable instances
• Verify geometric distances and connectivity constraints

References

• Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability, ND48, p.219.
• Lichtenstein, D. (1982). "Planar formulae and their uses." SIAM Journal on Computing, 11(2), pp. 329–343.

[GiggleLiu]

fix-issue changelog:

• Expanded from 721-char stub to full issue body with geometric construction
• Added variable gadgets (true/false points), clause gadgets (center + bridge points), distance threshold B=2.5
• Added example: n=3 vars, m=1 clause with concrete point coordinates and bridge chains
• Noted overhead has no clean closed-form (depends on planar embedding distances and bridge point count)
• Noted MinimumGeometricConnectedDominatingSet -> ILP companion rule needed
• Flagged Codex verification needed: geometric separation hypotheses not fully proved
• Removed specialization note (Planar3Satisfiability model exists in codebase)