[Rule] HamiltonianPath to DegreeConstrainedSpanningTree

[isPANN]

Source: HamiltonianPath
Target: DegreeConstrainedSpanningTree

Motivation: Establishes NP-completeness of DEGREE-CONSTRAINED SPANNING TREE for any fixed K >= 2 via reduction from HAMILTONIAN PATH. When K = 2, a spanning tree with maximum degree 2 is exactly a Hamiltonian path. This is a trivial identity reduction for K = 2 and shows that even the most restrictive degree bound already captures NP-hardness.
Reference: Garey & Johnson, Computers and Intractability, ND1, p.206

GJ Source Entry

[ND1] DEGREE-CONSTRAINED SPANNING TREE
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.

Reduction Algorithm

Given a HAMILTONIAN PATH instance G = (V, E) with n = |V| vertices:

1. Graph preservation: Keep G = (V, E) unchanged.

2. Degree bound: Set K = 2.

3. Equivalence: A spanning tree with maximum degree at most 2 is a path visiting all vertices, i.e., a Hamiltonian path.

Correctness:

• (Forward) If G has a Hamiltonian path, the path edges form a spanning tree where every vertex has degree at most 2 (endpoints have degree 1, interior vertices have degree 2).
• (Backward) If G has a spanning tree T with max degree <= 2, then T is a path (a connected acyclic graph with max degree 2 is a path). Since T spans all vertices, it is a Hamiltonian path.

For general K >= 3: The NP-completeness proof uses a more elaborate gadget reduction. For each vertex v in the original HP instance, replace v with a gadget that limits the effective degree while preserving path structure. However, the base case K = 2 is the direct identity reduction.

Size Overhead

Symbols:

• n = num_vertices of source graph G
• m = num_edges of source graph G

Target metric (code name)	Polynomial (using symbols above)
num_vertices	num_vertices
num_edges	num_edges

Derivation: For K = 2, the graph is completely unchanged. The degree bound K = 2 is a constant parameter.

Validation Method

• Closed-loop test: reduce HamiltonianPath instance to DegreeConstrainedSpanningTree with K = 2, solve with BruteForce, extract spanning tree, verify it is a valid Hamiltonian path.
• Negative test: use a graph with no Hamiltonian path (e.g., Petersen graph), verify no degree-2 spanning tree exists.
• For K > 2: verify that any Hamiltonian path is also a valid degree-K spanning tree (monotonicity: relaxing K makes the problem easier).
• Identity check: source and target graphs are identical.

Example

Source instance (HamiltonianPath):
Graph G with 5 vertices {0, 1, 2, 3, 4} and 7 edges:

• Edges: {0,1}, {0,3}, {1,2}, {1,3}, {2,3}, {2,4}, {3,4}
• Hamiltonian path: 0 -- 1 -- 2 -- 4 -- 3 (check: {0,1} yes, {1,2} yes, {2,4} yes, {4,3} yes)

Constructed target instance (DegreeConstrainedSpanningTree):

• Graph: G (unchanged, 5 vertices, 7 edges)
• Degree bound: K = 2

Solution mapping:

• Spanning tree: edges {0,1}, {1,2}, {2,4}, {4,3}
• Degree check: 0:1, 1:2, 2:2, 3:1, 4:2. Maximum degree = 2 <= K = 2.
• This spanning tree is the Hamiltonian path 0 -- 1 -- 2 -- 4 -- 3.

Negative example:
Graph G' = K_{1,4} (star with center 0, leaves 1,2,3,4) plus edge {1,2}.

• Edges: {0,1}, {0,2}, {0,3}, {0,4}, {1,2}
• No Hamiltonian path: vertex 0 has degree 4 in G', but in any spanning path, internal vertex 0 needs degree exactly 2. Paths through 0: ...--0--... can only use 2 of 0's 4 edges. Vertices 3 and 4 are only connected to 0, so both must be adjacent to 0 in any spanning tree, but then a degree-2 tree can't include 1 and 2 through 0. Check: paths like 3--0--4--?--? fail (4 only connects to 0). Answer: NO.

References

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

[GiggleLiu]

Implemented in PR #999.