[Model] MinimumCapacitatedSpanningTree

[isPANN]

Motivation

MINIMUM CAPACITATED SPANNING TREE (ND5) from Garey & Johnson, A2. Given a weighted graph with a designated root, vertex requirements, and an edge capacity, find a spanning tree rooted at a designated vertex that minimizes total edge weight, subject to subtree capacity constraints. NP-hard in the strong sense, even with all requirements equal to 1 and capacity equal to 3. A fundamental model in capacitated network design and facility location.

Definition

Name: MinimumCapacitatedSpanningTree
Reference: Garey & Johnson, Computers and Intractability, A2 ND5; Papadimitriou 1978

Mathematical definition:

INSTANCE: Graph G = (V, E), weight function w: E → Z⁺, designated root vertex v₀ ∈ V, requirement function r: V \ {v₀} → Z⁺, positive integer c (capacity).
OBJECTIVE: Find a spanning tree T = (V, E') for G that minimizes Σ_{e ∈ E'} w(e), subject to: for each edge e ∈ E', if U(e) denotes the set of vertices whose unique path to v₀ in T passes through e, then Σ_{u ∈ U(e)} r(u) ≤ c.

Variables

• Count: m = |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 rooted at v₀, every edge must carry at most capacity c worth of requirements from its subtree, and the total weight is minimized.

Schema

Type name: MinimumCapacitatedSpanningTree
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 ∈ E
root	usize	The designated root vertex v₀
requirements	Vec<W>	Requirement r(v) for each vertex v (r(v₀) = 0)
capacity	W::Sum	The edge capacity bound c

Complexity

• Best known exact algorithm: NP-hard in the strong sense (Papadimitriou, "The complexity of the capacitated tree problem," Networks 8, 217–230, 1978), so no pseudo-polynomial algorithm unless P = NP. Exact methods use branch-and-bound or branch-and-cut with ILP formulations. No known improvement over O*(2^num_edges) for general instances.
• Special cases:
  • All requirements = 1, capacity = 3: still NP-hard (Papadimitriou 1978).
  • Capacity ≥ Σ r(v): reduces to minimum spanning tree (polynomial).

Extra Remark

Full book text:

INSTANCE: Graph G = (V, E), a weight w(e) ∈ Z⁺ for each e ∈ E, a "root" vertex v₀ ∈ V, a requirement r(v) ∈ Z₀⁺ for each v ∈ V - {v₀}, and positive integers c ("capacity") and B ("bound").
QUESTION: Is there a spanning tree T = (V, E') for G such that Σ_{e ∈ E'} w(e) ≤ B and such that for each e ∈ E', if U(e) is the set of vertices whose paths to v₀ pass through e, then Σ_{u ∈ U(e)} r(u) ≤ c?

Reference: [Papadimitriou, 1976c]. Transformation from 3-SATISFIABILITY.
Comment: NP-complete in the strong sense, and remains so even if all requirements are 1 and c = 3.

Note: The original G&J formulation is a decision problem with weight bound B. We use the equivalent optimization formulation: minimize total edge weight subject to capacity constraints.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all spanning trees, root each at v₀, compute subtree requirement sums for every edge, check capacity constraints, track minimum weight.)
• It can be solved by reducing to integer programming. (ILP with binary edge variables, multi-commodity flow for routing, capacity constraints on each edge, minimize total weight.) See companion issue [Rule] MinimumCapacitatedSpanningTree to ILP #966.
• Other:

Reduction Rule Crossref

• [Rule] MinimumCapacitatedSpanningTree to ILP #966 — [Rule] MinimumCapacitatedSpanningTree to ILP (direct ILP formulation)

Example Instance

Input:
Graph G with V = {v0, v1, v2, v3, v4} (n = 5), root v₀ = v0, capacity c = 3.
Requirements: r(v1) = 1, r(v2) = 1, r(v3) = 1, r(v4) = 1.

Edges with weights:

• (v0,v1): w=2, (v0,v2): w=1, (v0,v3): w=4
• (v1,v2): w=3, (v1,v4): w=1
• (v2,v3): w=2, (v2,v4): w=3
• (v3,v4): w=1

Optimal tree T: edges {(v0,v1), (v0,v2), (v1,v4), (v3,v4)}, total weight = 2+1+1+1 = 5.
Rooted at v0, the tree structure is: v0→v1→v4→v3 and v0→v2.

• Edge (v0,v1): subtree {v1, v4, v3}, Σr = 3 ≤ 3 ✓
• Edge (v0,v2): subtree {v2}, Σr = 1 ≤ 3 ✓
• Edge (v1,v4): subtree {v4, v3}, Σr = 2 ≤ 3 ✓
• Edge (v3,v4): subtree {v3}, Σr = 1 ≤ 3 ✓

Suboptimal feasible tree: edges {(v0,v1), (v0,v2), (v1,v4), (v2,v3)}, weight = 2+1+1+2 = 6.

• Edge (v0,v1): subtree {v1, v4}, Σr = 2 ≤ 3 ✓
• Edge (v0,v2): subtree {v2, v3}, Σr = 2 ≤ 3 ✓

Infeasible tree: edges {(v0,v2), (v1,v2), (v2,v3), (v3,v4)}, weight = 1+3+2+1 = 7.

• Edge (v0,v2): subtree {v2, v1, v3, v4}, Σr = 4 > 3 ✗ (all non-root vertices route through this edge)

Expected Outcome

Optimal value: Min(5) — the minimum total weight of a feasible capacitated spanning tree is 5. Out of 45 spanning trees, 21 are feasible with 8 distinct weight values (5, 6, 7, 8, 9, 10, 11, 12).

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	No planned reduction to/from any existing problem mentioned
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	Complexity bound is a generic fallback, not the best known algorithm
Well-written	❌ Fail	Missing expected outcome section; example quality issues

Overall: 1 passed, 1 warning, 2 failed

---

Usefulness

The problem CapacitatedSpanningTree does not yet exist in the reduction graph (confirmed via pred show). However, the issue body does not mention any planned reduction rule connecting this problem to existing problems in the graph. The "How to solve" section only checks brute-force and leaves ILP unchecked, without linking a companion [Rule] CapacitatedSpanningTree to ILP issue or any other reduction.

Fail: Orphan node — a problem without any planned reduction rule has no value in the reduction graph. Add at least one planned reduction to/from an existing problem (e.g., a direct ILP formulation via flow variables, or a reduction from/to an existing network design problem like SteinerTreeInGraphs).

Non-trivial

Pass. This problem has genuinely distinct feasibility constraints from all existing problems in the codebase. While there are other spanning-tree-related problems (IsomorphicSpanningTree, KthBestSpanningTree, BoundedComponentSpanningForest, SteinerTree), none of them involve the capacitated routing constraint where the sum of vertex requirements routed through each edge must be bounded. The combination of a weight bound on the tree plus a capacity constraint on each edge's subtree load is unique.

Correctness

Reference verification:

• The issue cites "Papadimitriou 1976c" following the Garey & Johnson bibliography convention. The actual paper is: C.H. Papadimitriou, "The complexity of the capacitated tree problem," Networks 8, 217-230 (1978). The "1976c" label is the G&J internal citation key (likely reflecting a preprint or submission date), which is acceptable since the issue is directly referencing G&J's appendix entry ND5. The paper does prove NP-completeness of the capacitated spanning tree problem, including the special case with all requirements equal to 1 and capacity equal to 3. Verified.

• The claim of NP-completeness in the strong sense and the reduction from 3-SATISFIABILITY match established literature. Verified.

Complexity bound:

• The issue proposes complexity string "2^num_vertices", which is the trivial brute-force bound (enumerate all subsets of edges). This is not the best known exact algorithm. For spanning tree enumeration problems, the number of spanning trees can be computed via Kirchhoff's theorem, and exact algorithms for constrained spanning trees typically use dynamic programming. The issue itself acknowledges this is generic ("no known improvement over O*(2^n) for general instances") but does not cite any specific algorithm or paper for this bound.

Warn: The complexity string should reference a concrete algorithm. If no better bound is known, this should be explicitly stated with a citation to a survey (e.g., the chapter on CMST in the Handbook of Combinatorial Optimization). Note that 2^num_vertices may be loose — the search space is subsets of edges forming spanning trees, bounded by 2^|E| but in practice much smaller.

Example verification:
The example instance was independently verified via brute-force enumeration of all spanning trees:

• c=2, B=7: No feasible spanning tree exists (confirmed, all 11 spanning trees fail either weight or capacity).
• c=4, B=7: Tree {(0,1),(1,2),(2,4),(3,4)} with weight 6 is feasible (confirmed). Example is correct.

Well-written

4a: Information Completeness

Section	Status
Motivation	✅ Present and substantive
Name	✅ CapacitatedSpanningTree — correct naming for a feasibility/decision problem
Reference	✅ Garey & Johnson ND5, Papadimitriou 1976c
Definition	✅ Formal INSTANCE/QUESTION format
Variables	✅ Count, domain, meaning specified
Schema	✅ Field table with types
Complexity	⚠️ Generic bound without specific algorithm citation
How to solve	⚠️ Only brute-force checked; ILP formulation described in notes but not checked or linked
Example Instance	✅ Present with worked analysis
Expected Outcome	❌ Missing — the issue shows two scenarios (c=2 NO, c=4 YES) but does not clearly state a single expected outcome with a concrete valid solution and justification

4b: Definition Completeness
The definition is precise, using the standard G&J INSTANCE/QUESTION format. All constraints are mathematically stated. Pass.

4c: Symbol Consistency
Symbols are consistent between the definition, variables, and schema sections. The schema field names (root, requirements, capacity, weight_bound) match the definition's parameters. Pass.

4d: Example Quality

Issues found:

1. No single clear expected outcome: The example presents two parameter settings (c=2 and c=4) but the Expected Outcome section is missing. For a satisfaction problem, there should be one concrete instance with a clearly stated satisfying solution and brief justification of why it satisfies all constraints, OR a clear NO answer with justification. The dual-scenario presentation is pedagogically useful but does not meet the template requirement.

2. Round-trip testability concern: For the YES case (c=4, B=7), there are 6 feasible spanning trees out of 11 total. This is borderline — the NO case (c=2) is better for testing since it exercises all constraints, but a YES case with a unique or near-unique solution would be stronger for round-trip testing.

3. The issue uses T4 for the c=4 case but claims edge {1,2} carries load 3: This is actually correct (U({1,2}) = {2,3,4}, sum of requirements = 3), verified independently.

Fail items:

• Missing Expected Outcome section (template requirement)
• No planned reductions mentioned (affects both Usefulness and How-to-solve completeness)

Recommendations

• Add an Expected Outcome section with a single canonical instance. Suggestion: use the c=4, B=7 parameters and state the satisfying tree T4 = {(0,1),(1,2),(2,4),(3,4)} with weight 6, showing all capacity constraints are met.
• Add at least one planned reduction. A natural candidate is a direct CapacitatedSpanningTree -> ILP reduction using binary edge variables x_e, multi-commodity flow variables for routing requirements, capacity constraints, and a total weight constraint. The issue already sketches this in the "How to solve" notes.
• Research whether a tighter complexity bound exists. Consider citing Gavish (1983) or Gouveia (1993) for ILP formulations, or the branch-and-bound approach of Malik & Yu (1993).

[isPANN]

Converted from decision to optimization framing: renamed to MinimumCapacitatedSpanningTree, removed weight bound B, objective is now to minimize total edge weight subject to capacity constraints. Removed weight_bound field from schema. Value type is Min<i32>.