[Model] DegreeConstrainedSpanningTree

[isPANN]

Motivation

DEGREE-CONSTRAINED SPANNING TREE (ND1) from Garey & Johnson, A2. Given a graph G and a positive integer K, does G have a spanning tree with maximum vertex degree at most K? NP-complete for any fixed K >= 2 (when K = 2, the problem is equivalent to Hamiltonian Path). Applications in network design where hub congestion must be bounded.

Associated rules:

• [Rule] HamiltonianPath to DegreeConstrainedSpanningTree #911: HamiltonianPath → DegreeConstrainedSpanningTree (K=2 equivalence; NP-completeness proof from G&J)

Definition

Name: DegreeConstrainedSpanningTree
Reference: Garey & Johnson, Computers and Intractability, A2 ND1

Mathematical definition:

INSTANCE: Graph G = (V, E), positive integer K <= |V| - 1.
QUESTION: Does G have a spanning tree T = (V, E') with E' subset of E such that every vertex in T has degree at most K?

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 tree spanning all vertices, and every vertex must have degree at most K in the tree.

Schema

Type name: DegreeConstrainedSpanningTree
Variants: graph: SimpleGraph

Field	Type	Description
graph	SimpleGraph	The input graph G = (V, E)
max_degree	usize	The maximum degree bound K

Notes:

• This is a feasibility (decision) problem: Value = Or.
• Key getter methods: num_vertices() (= |V|), num_edges() (= |E|), max_degree() (= K).

Complexity

• Decision complexity: NP-complete for any fixed K >= 2 (Garey & Johnson; transformation from Hamiltonian Path).
• Best known exact algorithm: For K = 2, equivalent to Hamiltonian Path: O*(1.657^n) randomized time (Bjorklund 2014). For general K >= 3, dynamic programming approaches run in O*(2^n) time.
• Concrete complexity expression: "2^num_vertices" (for declare_variants!; general case)
• Special cases:
  • K = 1: trivially NO for |V| >= 3 (a tree on >= 3 vertices must have a vertex of degree >= 2).
  • K = 2: equivalent to Hamiltonian Path.
  • K >= |V| - 1: trivially YES if G is connected (any spanning tree suffices).
• References:
  • M.R. Garey and D.S. Johnson (1979). Computers and Intractability. W.H. Freeman.
  • A. Bjorklund (2014). "Determinant Sums for Undirected Hamiltonicity." SIAM J. Comput. 43(1), pp. 280-299.

Extra Remark

Full book text:

INSTANCE: Graph G = (V, E), positive integer K <= |V|.
QUESTION: Does G have a spanning tree with maximum degree K or less?

Reference: Transformation from HAMILTONIAN PATH.
Comment: NP-complete for any fixed K >= 2. When K = 2, the problem is equivalent to HAMILTONIAN PATH.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all (n-1)-edge subsets of E that form a spanning tree; check the maximum degree constraint.)
• It can be solved by reducing to integer programming.
• Other:

Example Instance

Input:
G with V = {0, 1, 2, 3, 4} and 7 edges: {0,1}, {0,2}, {0,3}, {1,2}, {1,4}, {2,3}, {3,4}.

K = 2 (Hamiltonian path):
Spanning tree: 4—1—2—0—3. Edges: {1,4}, {1,2}, {0,2}, {0,3}.
Degrees: v0=2, v1=2, v2=2, v3=1, v4=1. Maximum degree = 2 ≤ K. ✓
Answer: YES.

K = 3:
Spanning tree: edges {0,1}, {0,2}, {0,3}, {1,4}.
Degrees: v0=3, v1=2, v2=1, v3=1, v4=1. Maximum degree = 3 ≤ K. ✓
Answer: YES.

K = 1:
Impossible for |V| = 5 — a tree on 5 vertices has 4 edges, so some vertex must have degree ≥ 2.
Answer: NO.

Python validation script

from collections import defaultdict

def is_spanning_tree(n, edges):
    adj = defaultdict(set)
    for u, v in edges:
        adj[u].add(v); adj[v].add(u)
    visited = set()
    queue = [0]
    while queue:
        node = queue.pop(0)
        if node in visited: continue
        visited.add(node)
        for nb in adj[node]:
            if nb not in visited: queue.append(nb)
    return len(visited) == n and len(edges) == n - 1

def max_degree(n, edges):
    deg = [0] * n
    for u, v in edges:
        deg[u] += 1; deg[v] += 1
    return max(deg)

# K=2: Hamiltonian path 4-1-2-0-3
tree_k2 = [(1,4), (1,2), (0,2), (0,3)]
assert is_spanning_tree(5, tree_k2)
assert max_degree(5, tree_k2) == 2
print("K=2: valid spanning tree, max degree 2")

# K=3
tree_k3 = [(0,1), (0,2), (0,3), (1,4)]
assert is_spanning_tree(5, tree_k3)
assert max_degree(5, tree_k3) == 3
print("K=3: valid spanning tree, max degree 3")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	No planned reduction connecting this problem to the existing graph
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	Complexity bound 2^num_vertices is the naive bound; better may exist for specific K
Well-written	❌ Fail	Missing Expected Outcome section; no reduction crossrefs

Overall: 1 passed, 2 failed, 1 warning

---

Usefulness

The problem DegreeConstrainedSpanningTree does not yet exist in the reduction graph. However, the issue body mentions no concrete planned reduction rules connecting this problem to any existing problem. The "How to solve" section only checks brute-force and does not reference any [Rule] issue.

The problem is related to HamiltonianPath (K=2 is equivalent to Hamiltonian Path), IsomorphicSpanningTree, and BoundedComponentSpanningForest — all of which exist in the codebase. At minimum, the issue should describe a planned reduction from HamiltonianPath or HamiltonianCircuit (both already implemented) to establish graph connectivity. Without at least one planned reduction, this would be an orphan node with no value in the reduction graph.

Verdict: Fail — orphan node. Add at least one planned reduction to/from an existing problem (e.g., HamiltonianPath reduces to DegreeConstrainedSpanningTree with K=2).

Non-trivial

This problem has genuinely distinct feasibility constraints from all existing problems in the codebase. While HamiltonianPath is the K=2 special case, DegreeConstrainedSpanningTree generalizes this to arbitrary degree bounds K, which changes the problem structure meaningfully. It is not a trivial variant or renaming of any existing model.

Verdict: Pass

Correctness

Reference verification:

• Garey & Johnson, Computers and Intractability, A2 ND1 — Verified. This is a well-known NP-complete problem in the standard reference. The claim that it is NP-complete for any fixed K >= 2 via reduction from Hamiltonian Path is correct.

Complexity verification:

• The issue claims O*(1.657^n) for K=2 citing "Bjorklund 2014". The Bjorklund 2014 paper ("Determinant Sums for Undirected Hamiltonicity", SIAM J. Computing 43(1):280-299) is already in the project bibliography and indeed achieves O*(1.657^n) randomized time for Hamiltonian cycle/path detection. This is correct.
• The general complexity string "2^num_vertices" is the naive brute-force bound (enumerate all spanning trees). This is not the best known algorithm — it is simply the trivial bound. For general K >= 3, more sophisticated approaches may improve on this, though the issue does not cite any specific faster algorithm. Recent work by Bojikian et al. (arXiv:2503.15226, 2025) studies fine-grained complexity parameterized by treewidth but does not provide a simple O*(c^n) improvement for general graphs.

Verdict: Warn — the complexity string "2^num_vertices" is acceptable as a conservative bound but the issue should note this is the naive bound, not a best-known result. A recommendation is provided below.

Well-written

4a — Information Completeness:
The following required sections are missing or inadequate:

• Expected Outcome: The example section shows three cases (K=2, K=3, K=1) with YES/NO answers and spanning trees, but there is no dedicated "Expected Outcome" section with a concrete solution and brief justification as required by the template.
• Reduction crossrefs: No planned [Rule] issues are referenced.

4b — Definition Completeness:
The formal definition is clear and well-formed. Input (graph G, integer K), feasibility constraint (spanning tree with max degree <= K), and decision question are all precisely stated.

4c — Symbol and Notation Consistency:
Symbols are used consistently. G = (V, E), K, T = (V, E') are all properly defined and used throughout.

4d — Example Quality:
The examples are reasonable and illustrate the problem well across three values of K. The K=2 example explicitly constructs the Hamiltonian path, which exercises the core structure. However:

• The examples are spread across three separate K values rather than providing one focused instance with a definitive expected outcome.
• For a feasibility problem, the issue should clearly state one primary example with its solution and explain why it satisfies the constraints.

Verdict: Fail — missing Expected Outcome section.

Recommendations

• Add at least one planned reduction, such as: HamiltonianPath -> DegreeConstrainedSpanningTree (set K=2) or DegreeConstrainedSpanningTree -> ILP (binary edge variables with connectivity and degree constraints).
• Consider whether a better complexity bound than the naive 2^num_vertices exists for general K. The K=2 case has O*(1.657^n); it is worth investigating whether inclusion-exclusion or algebraic techniques extend to K >= 3.
• Add a dedicated Expected Outcome section with one primary example instance, the concrete solution (which edges form the spanning tree), and a brief justification of why it satisfies the degree constraint.

[isPANN]

Fix-issue changelog

• Associated rules: Linked rule [Rule] HamiltonianPath to DegreeConstrainedSpanningTree #911 (HamiltonianPath → DegreeConstrainedSpanningTree).
• Complexity: Added concrete expression "2^num_vertices" for declare_variants!; reformatted with decision complexity and references.
• Schema notes: Added getter methods and Value = Or.
• Example: Added ✓ marks, explicit degree calculations, Python validation script.

Applied by /fix-issue.