[Model] BoundedDiameterSpanningTree

[isPANN]

Motivation

BOUNDED DIAMETER SPANNING TREE (ND4) from Garey & Johnson, A2. Given a weighted graph, a weight bound B, and a diameter bound D, find a spanning tree with total weight at most B and diameter (longest path in edges) at most D. NP-complete for any fixed D >= 4, even with edge weights restricted to {1, 2}. Polynomial for D <= 3 or when all weights are equal. Applications in communication network design where both cost and latency must be bounded.

Associated reduction rules:

• [Rule] ExactCoverBy3Sets to BoundedDiameterSpanningTree #913: ExactCoverBy3Sets -> BoundedDiameterSpanningTree (GJ reference reduction from X3C)

Definition

Name: BoundedDiameterSpanningTree
Reference: Garey & Johnson, Computers and Intractability, A2 ND4

Mathematical definition:

INSTANCE: Graph G = (V, E), weight function w: E -> Z+, positive integers B and D.
QUESTION: Is there a spanning tree T = (V, E') for G such that the sum of weights sum_{e in E'} w(e) <= B and such that T contains no path of more than D edges?

Variables

• Count: |E| (one binary variable per edge)
• Per-variable domain: {0, 1}
• Meaning: Whether each edge is included in the spanning tree. The selected edges must form a spanning tree with total weight at most B and diameter at most D.

Schema

Type name: BoundedDiameterSpanningTree
Variants: graph: SimpleGraph, weight: i32

Field	Type	Description
graph	SimpleGraph	The input graph G = (V, E)
weights	Vec<W>	Edge weights w(e) for each edge e in E
weight_bound	W::Sum	The total weight bound B
diameter_bound	usize	The maximum allowed diameter D (in number of edges)

Getters (for overhead expressions):

• num_vertices() -> graph.num_vertices()
• num_edges() -> graph.num_edges()
• weight_bound() -> weight_bound
• diameter_bound() -> diameter_bound

Complexity

• Best known exact algorithm: NP-complete for any fixed D >= 4 (Garey and Johnson, 1979). Solvable by enumerating all spanning trees via Kirchhoff's matrix-tree theorem; the number of spanning trees is at most n^(n-2) by Cayley's formula. For each tree, checking the weight and diameter constraints takes O(n) time. Thus the brute-force complexity is O(n^(n-1)).
• Special cases:
  • D <= 3: polynomial time (Garey and Johnson).
  • All weights equal: polynomial time (reduces to finding a spanning tree with bounded diameter, solvable via BFS-based approaches).
  • D >= n-1: equivalent to minimum spanning tree (polynomial).
  • Weights in {1, 2}: still NP-complete for D >= 4.
• declare_variants! complexity string: "num_vertices ^ num_vertices"

Extra Remark

Full book text:

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.

How to solve

• It can be solved by (existing) bruteforce.
• It can be solved by reducing to integer programming.
• Other:

Note: Bruteforce enumerates all spanning trees, checks that total weight <= B and the longest simple path (diameter) has at most D edges. ILP formulation: binary variables x_e per edge, connectivity and subtour-elimination constraints, weight constraint sum w_e * x_e <= B, and diameter constraint via layered flow variables.

Example Instance

Consider the graph G with 5 vertices {0, 1, 2, 3, 4} and 7 edges with weights:

• {0,1}: w=1, {0,2}: w=2, {0,3}: w=1, {1,2}: w=1, {1,4}: w=2, {2,3}: w=1, {3,4}: w=1

YES case (B = 5, D = 3):

• Tree T = {(0,1), (0,3), (2,3), (3,4)}. Weight = 1+1+1+1 = 4 <= 5. Diameter: longest shortest path is from vertex 2 to vertex 1: 2--3--0--1 = 3 edges, and from vertex 2 to vertex 4: 2--3--4 = 2 edges. Maximum = 3 <= D = 3. PASSES.
• Expected outcome: YES. Solution: edge set {(0,1), (0,3), (2,3), (3,4)} with total weight 4 and diameter 3.

NO case (B = 4, D = 2):

• All spanning trees with weight <= 4 have diameter >= 3: e.g. {(0,1), (0,3), (1,2), (3,4)} has weight 4 but diameter 4; {(0,1), (0,3), (2,3), (3,4)} has weight 4 but diameter 3. No vertex is adjacent to all others, so no star exists and diameter 2 is impossible.
• Expected outcome: NO.

Validation script:

from itertools import combinations
from collections import deque

edges = [(0,1,1),(0,2,2),(0,3,1),(1,2,1),(1,4,2),(2,3,1),(3,4,1)]
n = 5
edge_set = {(min(u,v),max(u,v)): w for u,v,w in edges}

def is_spanning_tree(sel):
    if len(sel) != n-1: return False
    adj = {i:[] for i in range(n)}
    for u,v in sel:
        adj[u].append(v); adj[v].append(u)
    vis = set(); q = deque([0]); vis.add(0)
    while q:
        x = q.popleft()
        for nb in adj[x]:
            if nb not in vis: vis.add(nb); q.append(nb)
    return len(vis) == n

def diameter(sel):
    adj = {i:[] for i in range(n)}
    for u,v in sel:
        adj[u].append(v); adj[v].append(u)
    mx = 0
    for s in range(n):
        d = [-1]*n; d[s]=0; q=deque([s])
        while q:
            x=q.popleft()
            for nb in adj[x]:
                if d[nb]==-1: d[nb]=d[x]+1; q.append(nb)
        mx = max(mx, max(d))
    return mx

def weight(sel): return sum(edge_set[(min(u,v),max(u,v))] for u,v in sel)

pairs = [(min(u,v),max(u,v)) for u,v,_ in edges]
trees = [list(c) for c in combinations(pairs, n-1) if is_spanning_tree(list(c))]

# YES: B=5, D=3
yes = [t for t in trees if weight(t)<=5 and diameter(t)<=3]
assert len(yes) > 0, "YES case should be feasible"
assert any(set(t)=={(0,1),(0,3),(2,3),(3,4)} for t in yes)

# NO: B=4, D=2
no = [t for t in trees if weight(t)<=4 and diameter(t)<=2]
assert len(no) == 0, "NO case should be infeasible"
print("All assertions passed.")

References

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

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	No reduction to/from any existing problem mentioned — orphan node
Non-trivial	✅ Pass	Distinct feasibility constraints from all 126 existing problems
Correctness	⚠️ Warn	G&J reference valid; complexity string 2^num_edges is a very loose bound
Well-written	❌ Fail	Missing Expected Outcome section; complexity string needs a specific algorithm citation

Overall: 1 passed, 1 warning, 2 failed

---

Usefulness

The problem BoundedDiameterSpanningTree does not currently exist in the codebase (confirmed via pred show). However, the issue does not mention any concrete reduction rule connecting this problem to the existing reduction graph. Under "How to solve", only brute-force is checked. The note mentions an ILP formulation sketch but ILP is not checked and no companion [Rule] BoundedDiameterSpanningTree to ILP issue is linked.

A problem without any planned reduction rule has no value in the reduction graph. The issue must specify at least one concrete reduction to/from an existing problem (e.g., a reduction from X3C, Partition, or HamiltonianCircuit, or a direct ILP reduction with a linked companion issue).

Non-trivial

This is a genuinely distinct problem. The codebase has several spanning-tree-related problems (BoundedComponentSpanningForest, IsomorphicSpanningTree, KthBestSpanningTree) but none combine a diameter bound with a weight bound on spanning trees. The feasibility constraints (total weight <= B AND longest path <= D edges) are structurally different from all 126 existing problems.

Correctness

Reference verification: Garey & Johnson Computers and Intractability (1979), A2 ND4 is a valid reference and is already in the project bibliography (@book{garey1979}). The NP-completeness claim for D >= 4 (even with weights in {1, 2}) and polynomial solvability for D <= 3 or equal weights are consistent with G&J.

Complexity string concern: The stated complexity "2^num_edges" is described as "spanning tree enumeration" but this is an extremely loose upper bound. The number of spanning trees in a graph with n vertices and m edges is at most C(m, n-1), which is much smaller than 2^m. Additionally:

• No specific algorithm or paper is cited for this bound — it appears to be a hand-wave ("enumerating spanning trees and checking constraints").
• A tighter bound would be based on Cayley/Kirchhoff or on modern exact algorithms for constrained spanning tree problems.
• The mention of "FPT algorithms for bounded treewidth" is vague and uncited.

Recommendation: The complexity string should reference a concrete algorithm. If no better exact algorithm is known, a tighter naive bound based on the number of spanning trees (e.g., via matrix-tree theorem or Cayley's formula for complete graphs: n^(n-2)) would be more appropriate than 2^num_edges.

Well-written

Missing sections:

1. Expected Outcome: The example provides YES/NO answers but does not present a concrete valid solution in the standard format. The YES case (B=5, D=3) identifies tree T2 but should explicitly state: "Solution: edge set {(0,1), (0,2), (0,3), (3,4)} with total weight 5 and diameter 3."
2. Complexity section lacks a concrete cited algorithm — "O*(2^m) in the worst case" with no algorithm name, author, or paper is not sufficient. The skill requires "Best known algorithm with citation and a concrete complexity expression."

Example quality: The example with 5 vertices and 7 edges is reasonable in size. It exercises both the weight and diameter constraints and shows a YES and NO case. However:

• The YES case verification of diameter = 3 should be more rigorous (enumerate all pairs of vertices and show the longest path in T2 is 3 edges).
• Having both a YES and NO case is good, but for a feasibility problem, the example should also show at least one other spanning tree that satisfies weight but not diameter (already done with T1) and ideally one that satisfies diameter but not weight, to demonstrate both constraints are binding.

Notation: Symbols are reasonably consistent across sections. The Schema field types match the definition.

Recommendations

• Add at least one planned reduction (e.g., direct ILP formulation, or a reduction from/to an existing graph problem like HamiltonianCircuit or SteinerTree).
• Replace the complexity string with a tighter bound and cite a specific algorithm. Consider using num_vertices^num_vertices (Cayley bound) or a better parameterized bound.
• Add an explicit Expected Outcome subsection with the concrete solution for the YES case.

[isPANN]

Changelog (fix-issue)

Fixes applied to address check-issue failures:

1. Usefulness (was: Fail): Added Associated reduction rules section linking [Rule] ExactCoverBy3Sets to BoundedDiameterSpanningTree #913 (ExactCoverBy3Sets -> BoundedDiameterSpanningTree), the GJ reference reduction from X3C.

2. Correctness / Complexity (was: Warn): Replaced the loose 2^num_edges complexity string with num_vertices ^ num_vertices, based on Cayley's formula upper bound on spanning tree count (n^(n-2) trees, O(n) check per tree). Removed vague "FPT for bounded treewidth" claim.

3. Well-written (was: Fail):

   • Added Getters subsection to Schema with num_vertices(), num_edges(), weight_bound(), diameter_bound().
   • Added Expected Outcome lines for both YES and NO cases.
   • Fixed the NO case: the original B=4, D=3 was actually YES (two feasible trees exist). Replaced with B=4, D=2 which is genuinely infeasible (no spanning tree has diameter <= 2 in this graph).
   • Added a Python validation script that exhaustively verifies both cases.
   • Cleaned up the YES case analysis with correct tree {(0,1),(0,3),(2,3),(3,4)} and explicit diameter verification.