[Rule] ExactCoverBy3Sets to BoundedDiameterSpanningTree

[isPANN]

Source: ExactCoverBy3Sets (X3C)
Target: BoundedDiameterSpanningTree
Motivation: Establishes NP-completeness of BOUNDED DIAMETER SPANNING TREE for any fixed D ≥ 4 via transformation from X3C. The diameter constraint on spanning trees arises in communication network design where latency (hop count) must be bounded alongside total cost.
Reference: Garey & Johnson, Computers and Intractability, ND4, p.206

GJ Source Entry

[ND4] BOUNDED DIAMETER SPANNING TREE
INSTANCE: Graph G = (V, E), a weight w(e) in Z+ for each e in E, positive integers B and D.
QUESTION: Is there a spanning tree T = (V, E') for G such that sum_{e in E'} w(e) <= B and such that T contains no path of more than D edges?
Reference: [Garey and Johnson, ----]. Transformation from X3C.
Comment: NP-complete for any fixed D >= 4, even if w(e) in {1, 2} for all e in E. Can be solved in polynomial time for D <= 3 or if all weights are equal.

Reduction Algorithm

Given an X3C instance with universe X = {0, 1, …, 3q−1} and collection C = [S₀, S₁, …, S_{m−1}] where each Sᵢ is a 3-element subset of X.

All weights are in {1, 2}, consistent with the Z⁺ requirement in the problem definition.

Vertex indexing

• r = 0
• v₁ = 1, v₂ = 2
• sᵢ = 3 + i for i ∈ [0, m−1]
• eⱼ = 3 + m + j for j ∈ [0, 3q−1]

Total vertices: n = 3 + m + 3q

Edge construction

The graph contains only the edges below; no other edges are present.

1. Forced-center path: (r, v₁) weight 1, (v₁, v₂) weight 1. Because dist(r, v₂) = 2, any feasible spanning tree of diameter ≤ 4 must keep every vertex within distance 2 of r.

2. Root-to-set edges: For each sᵢ: (r, sᵢ) weight 2. Choosing this edge corresponds to selecting set Sᵢ.

3. Set-to-element edges: If j ∈ Sᵢ: (sᵢ, eⱼ) weight 1. Each element connects through its covering set.

4. Set clique: For all 0 ≤ i < j < m: (sᵢ, sⱼ) weight 1. Unselected sets attach to selected ones cheaply.

Parameters

• D = 4
• B = 4q + m + 2

Explanation of B: q selected sets cost 2q; remaining m − q sets use clique edges costing m − q; 3q element edges cost 3q; forced path costs 2. Total: 2q + (m − q) + 3q + 2 = 4q + m + 2.

Size Overhead

Target metric (code name)	Expression
num_vertices	m + 3q + 3
num_edges	2 + m + 3m + m(m−1)/2
weight_bound	4q + m + 2
diameter_bound	4

Correctness

Forward direction (X3C has exact cover ⟹ BDST feasible)

Let {Sᵢ₁, …, Sᵢ_q} be an exact cover. Construct the spanning tree:

• Forced-center: (r, v₁), (v₁, v₂) — cost 2
• Selected sets: (r, sᵢₖ) for k = 1, …, q — cost 2q
• Elements: each eⱼ connects to its unique covering sᵢₖ — cost 3q
• Unselected sets: each connects to any selected sᵢₖ via clique edge — cost m − q
• Total weight: 2 + 2q + 3q + (m − q) = 4q + m + 2 = B ✓
• Diameter: set vertices at depth 1, elements at depth 2, all within distance 2 of r, so diameter ≤ 4 ✓

Backward direction (BDST feasible ⟹ X3C has exact cover)

Let T be a spanning tree with weight ≤ B and diameter ≤ 4.

Step 1 — radius constraint. Since dist(r, v₂) = 2, any vertex at distance ≥ 3 from r would be at distance ≥ 5 from v₂, contradicting diameter ≤ 4. Hence all vertices are within distance 2 of r.

Step 2 — element attachment. Element vertices connect only to set vertices (no other edges exist in the graph). So each eⱼ must be at depth 2: eⱼ → sᵢ → r, meaning sᵢ is directly connected to r.

Step 3 — budget counting. Let k be the number of root-to-set edges in T. The minimum cost is: k · 2 + (m − k) · 1 + 3q · 1 + 2 · 1 = k + m + 3q + 2. Feasibility requires k + m + 3q + 2 ≤ 4q + m + 2, so k ≤ q.

Step 4 — covering. Each selected set covers at most 3 elements. To cover all 3q elements, k ≥ q. Thus k = q. Since exactly q sets of size 3 must account for all 3q element attachments, every selected set contributes all three of its elements and no element belongs to two selected sets. Therefore the selected sets are pairwise disjoint and form an exact cover.

Solution Extraction

selected = {i for i in range(m) if (r, s(i)) ∈ T or (s(i), r) ∈ T}

These are the set vertices connected to r via weight-2 edges. The corresponding sets form the exact cover.

Validation Method

• Closed-loop: reduce X3C → BDST, solve, extract cover, verify
• Negative: X3C with no exact cover → BDST infeasible
• Tree validity: n−1 edges, connected, acyclic
• Weight ≤ B, diameter ≤ D
• Extraction: q sets, pairwise disjoint, union = X

Example

Source (X3C):
X = {0, 1, 2, 3, 4, 5}, q = 2.
C = [S₀={0,1,2}, S₁={3,4,5}, S₂={0,3,4}, S₃={1,2,5}].
Exact covers: {S₀, S₁} or {S₂, S₃}.

Constructed BDST (n=13, D=4, B=14):

• Vertices: r(0), v₁(1), v₂(2), s₀(3), s₁(4), s₂(5), s₃(6), e₀(7), e₁(8), e₂(9), e₃(10), e₄(11), e₅(12)
• Edges (24 total, all weights ∈ {1, 2}):
  • Forced: (0,1) w=1, (1,2) w=1
  • Root-to-set: (0,3) w=2, (0,4) w=2, (0,5) w=2, (0,6) w=2
  • Set-to-element: (3,7) w=1, (3,8) w=1, (3,9) w=1, (4,10) w=1, (4,11) w=1, (4,12) w=1, (5,7) w=1, (5,10) w=1, (5,11) w=1, (6,8) w=1, (6,9) w=1, (6,12) w=1
  • Clique: (3,4) w=1, (3,5) w=1, (3,6) w=1, (4,5) w=1, (4,6) w=1, (5,6) w=1

Solution (cover {S₀, S₁}):
Tree: (0,1)w=1, (1,2)w=1, (0,3)w=2, (0,4)w=2, (3,7)w=1, (3,8)w=1, (3,9)w=1, (4,10)w=1, (4,11)w=1, (4,12)w=1, (5,3)w=1, (6,4)w=1

• 12 edges, 13 vertices ✓
• Weight: 1+1+2+2+1+1+1+1+1+1+1+1 = 14 = B ✓
• Diameter: e₀(7)–s₀(3)–r(0)–s₁(4)–e₃(10) = 4 edges ✓

NO instance:
C = [S₀={0,1,2}, S₁={0,3,4}, S₂={1,3,5}, S₃={2,4,5}].
Every pair overlaps → no exact cover → BDST infeasible with B=14.

References

• [Garey and Johnson, 1979]: Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ND4, p.206.

[isPANN]

Rule Fix -- Failed

Verdict: needs major revision — the reduction direction (X3C → Bounded Diameter Spanning Tree) is correct, but the construction is fundamentally incomplete. This is not fixable with arithmetic patches; it requires replacing core gadget logic with the canonical construction.

Checklist results

#	Check	Verdict	Reason
1	Reduction direction	PASS	X3C ≤_p BDST is correct
2	Forward proof (yes→yes)	FAIL	Missing Y-clique means unselected set-vertices cannot be connected within budget
3	Backward proof (no→no)	FAIL	Argument incomplete due to broken gadget structure
4	Gadget completeness	FAIL	Missing two critical gadgets: (a) zero-cost clique among all set-vertices, (b) forced-center path r→v₁→v₂
5	Solution extraction	SUSPECT	Underspecified given missing gadgets
6	Polynomial time	PASS	Construction is polynomial
7	Overhead consistency	FAIL	Budget B only accounts for exact-cover edges; unselected set-vertices have no zero-cost connection mechanism
8	Example correctness	FAIL	Example self-exposes the bug: s₃, s₄ cannot join the spanning tree within budget after exact cover is selected
9	Type compatibility	PASS	Or→Min is valid
10	Objective/bound preservation	FAIL	Weight structure (1/2 weights + backup edges) diverges from canonical (0/1 costs); budget logic does not close
11	Target-instance validity	SUSPECT	Without Y-clique, graph connectivity under diameter constraint is not guaranteed
12	Undirected rerouting	N/A	Not a path-disjointness reduction

Core problems (4 items)

1. Missing Y-clique gadget: The canonical construction adds zero-cost edges among all set-vertices so that unselected sets can be connected to the spanning tree at no additional cost. Without this, selecting an exact cover leaves remaining set-vertices stranded outside the budget.

2. Wrong weight structure: Issue uses r→set weight 1, set→element weight 1 or 2, element→hub backup weight 2. Canonical construction: all edges cost 0 except r→Y edges which cost 1. The optimization target then equals "how many set-vertices are directly connected to r" = q (the cover size).

3. D=4 structural misunderstanding: The key constraint is that with diameter 4, the tree has height ≤ ⌊D/2⌋ = 2 from center r. Element vertices must reach r in ≤2 hops, so they must pass through a set-vertex that is directly connected to r. The forced-center path r→v₁→v₂ prevents any Y-vertex from usurping the center role.

4. Example self-contradicts: Budget is set to cover only exact-cover edges (2 hub-to-set + 6 set-to-element), but the remaining set-vertices s₃, s₄ still need to join the spanning tree. The issue itself identifies this gap but cannot resolve it — because the Y-clique mechanism is missing.

Canonical construction sketch (D=4 base case, from literature)

1. Element vertex for each x ∈ X; set vertex for each Yᵢ
2. Root r connected to every set vertex (cost 1)
3. Set vertex → element vertex if x ∈ Yᵢ (cost 0)
4. Complete graph (clique) among all set vertices (cost 0)
5. Forced-center path: r → v₁ → v₂ (cost 0)
6. Ask: ∃ spanning tree with diameter ≤ 4 and total cost = q?
7. Such a tree exists ⟺ X3C instance has an exact cover

Additional notes

• Terminology: issue writes "X3C" but the codebase model is ExactCoverBy3Sets; either X3C or X3S is fine but should be consistent
• The claim "even with weights restricted to {1,2}" appears in G&J catalog commentary but is not implemented by the current construction; should not be stated as if proven by the algorithm

Action required

This issue needs a major rewrite incorporating the canonical gadgets (Y-clique + forced center). The current construction is an intuitive sketch that does not close. Recommend consulting the original paper or a detailed textbook treatment before rewriting.

Leaving on OnHold for manual intervention.

[isPANN]

Rule Fix

Diagnosis:

• Gadget completeness (FAIL): Missing two critical structures: (a) zero-cost clique among set vertices allowing unselected sets to piggyback, (b) forced-center path r→v₁→v₂ ensuring r is the unique tree center
• Weight structure (FAIL): Original used ad-hoc 1/2 weights + backup edges; canonical construction uses {1,2} weights with clear semantic roles (hub-to-set=2, everything else=1)
• Budget logic (FAIL): Original budget only accounted for exact-cover edges, leaving unselected set vertices stranded; corrected B = 4q + m + 2 accounts for all tree edges
• Example (FAIL): Self-contradicted — acknowledged s₃, s₄ couldn't join tree within budget; fixed with complete example showing all 12 tree edges
• Correctness proof (FAIL): Was hand-waved; replaced with explicit forward/backward proofs
• Solution extraction (SUSPECT): Underspecified; now explicit (select set vertices with weight-2 edges to r)
• NO instance (missing): Added

Literature:

• Garey & Johnson ND4 (p.206): "Transformation from X3C" — the canonical {0,1}-weight construction with set clique + forced center, shifted to {1,2} to satisfy Z⁺ constraint

Changes:

• Rewrote reduction algorithm with correct gadgets (set clique, forced center path)
• Changed weights to {1,2} (hub-to-set=2, all others=1) satisfying G&J's Z⁺ requirement
• Corrected budget formula: B = 4q + m + 2 with derivation breakdown
• Added explicit forward and backward correctness proofs
• Rewrote example with full edge list and weight verification
• Added NO instance example
• Added solution extraction procedure
• Removed unsubstantiated "weights restricted to {1,2}" claim from motivation (now actually proven by the construction)

Smoke test:

• 131 checks passed across all buckets (ILP-based solver)
• Buckets: YES(1) + NO(1) + edge cases(3) + feasibility agreement(60/60) + extraction(43/43) + overhead(3) + structural validity(20/20)
• All edge weights verified ∈ {1,2}

[isPANN]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path ExactCoverBy3Sets → BoundedDiameterSpanningTree
Non-trivial	✅ Pass	Gadget construction: set clique, forced-center path, weight differentiation
Correctness	✅ Pass	G&J 1979 ND4 p.206 explicitly states "Transformation from X3C"
Well-written	✅ Pass	All sections complete, symbols consistent, YES+NO examples with verification

Overall: 4 passed, 0 failed, 0 warnings

---

Usefulness

No reduction path exists from ExactCoverBy3Sets to BoundedDiameterSpanningTree in the current graph. BDST currently has 0 incoming reductions, so this adds a new node to the reduction graph. Motivation is concrete (network design latency constraints).

Non-trivial

The construction involves three distinct gadgets: (1) set clique for zero-cost piggybacking of unselected sets, (2) forced-center path to fix the tree root, (3) weight differentiation (cost-2 hub edges vs cost-1 others) to encode the exact cover constraint. This is a genuine structural transformation.

Correctness

• Garey & Johnson 1979, ND4, p.206 — canonical reference for BOUNDED DIAMETER SPANNING TREE. The entry explicitly states "Transformation from X3C" and notes NP-completeness for D ≥ 4 with weights in {1,2}.
• The construction uses weights ∈ {1,2}, matching the G&J comment.
• Forward and backward proofs are explicit and complete.
• Budget analysis correctly derives k = q via double-counting.

Well-written

• Sections: All required sections present and substantive (Source, Target, Motivation, Reference, GJ Entry, Algorithm, Overhead, Correctness, Solution Extraction, Validation, Example).
• Algorithm: 6 numbered steps, fully implementable. Each step specifies exact vertices, edges, and weights.
• Symbols: q, m, r, v₁, v₂, sᵢ, eⱼ all defined before first use. Consistent across sections.
• Example: YES instance (|X|=6, m=4, two exact covers) and NO instance (every pair overlaps). Tree edges enumerated with weight verification. Non-trivial: 13 vertices, multiple feasible solutions with different costs.
• Overhead table: Field names num_vertices, num_edges, weight_bound, diameter_bound are reasonable. Note: BDST currently has no registered size getters; these will need to be added during implementation.

Note

• The overhead expressions use exact formulas (not big-O), which is the preferred format for this project.