[Rule] HamiltonianPath to IsomorphicSpanningTree

[isPANN]

Source: HamiltonianPath
Target: IsomorphicSpanningTree

Motivation: Establishes NP-completeness of ISOMORPHIC SPANNING TREE via a direct embedding from HAMILTONIAN PATH. When the target tree T is a path P_n, the problem IS Hamiltonian Path. This is one of the simplest reductions in the G&J catalog: the graph is unchanged, and only the tree parameter is constructed. The problem remains NP-complete for other tree types including full binary trees and 3-stars (Papadimitriou and Yannakakis 1978).
Reference: Garey & Johnson, Computers and Intractability, ND8, p.207; Papadimitriou and Yannakakis 1978

GJ Source Entry

[ND8] ISOMORPHIC SPANNING TREE
INSTANCE: Graph G=(V,E), tree T=(V_T,E_T).
QUESTION: Does G contain a spanning tree isomorphic to T?
Reference: Transformation from HAMILTONIAN PATH.
Comment: Remains NP-complete even if (a) T is a path, (b) T is a full binary tree [Papadimitriou and Yannakakis, 1978], or if (c) T is a 3-star (that is, V_T={v_0} union {u_i,v_i,w_i: 1<=i<=n}, E_T={{v_0,u_i},{u_i,v_i},{v_i,w_i}: 1<=i<=n}) [Garey and Johnson, ----]. Solvable in polynomial time by graph matching if G is a 2-star.

Reduction Algorithm

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

1. Graph preservation: Keep G = (V, E) unchanged as the host graph.
2. Tree construction: Set T = P_n, the path graph on n vertices. T = ({t_0, ..., t_{n-1}}, {{t_i, t_{i+1}} : 0 <= i <= n-2}).
3. Equivalence: G has a Hamiltonian path if and only if G has a spanning tree isomorphic to P_n.
4. Solution extraction: An isomorphism phi: V(P_n) -> V(G) mapping the path tree to a spanning subgraph of G gives the Hamiltonian path as phi(t_0), phi(t_1), ..., phi(t_{n-1}).

Correctness:

• (Forward) A Hamiltonian path v_0, v_1, ..., v_{n-1} in G is a spanning tree isomorphic to P_n.
• (Backward) A spanning tree of G isomorphic to P_n has maximum degree 2 and is connected, hence is a Hamiltonian path.

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 (host graph)	num_vertices
num_edges (host graph)	num_edges
tree_vertices	num_vertices
tree_edges	num_vertices - 1

Derivation: Host graph is unchanged. Target tree P_n has n vertices and n-1 edges.

Validation Method

• Closed-loop test: construct graph G, reduce to (G, P_n), solve with BruteForce, extract Hamiltonian path from the isomorphism, verify all vertices visited exactly once using only edges of G.
• Negative test: use a graph with no Hamiltonian path (e.g., Petersen graph), verify no spanning tree isomorphic to P_n exists.
• Identity check: host graph in target instance is identical to source graph.

Example

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

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

Constructed target instance (IsomorphicSpanningTree):

• Host graph: G (unchanged)
• Target tree: T = P_5 with vertices {t_0, t_1, t_2, t_3, t_4} and edges {t_0,t_1}, {t_1,t_2}, {t_2,t_3}, {t_3,t_4}

Solution mapping:

• Spanning tree of G isomorphic to P_5: edges {0,1}, {1,3}, {3,4}, {4,2}
• Isomorphism: 0->t_0, 1->t_1, 3->t_2, 4->t_3, 2->t_4
• Extracted Hamiltonian path: 0 -- 1 -- 3 -- 4 -- 2

References

• [Papadimitriou and Yannakakis, 1978]: Christos H. Papadimitriou and M. Yannakakis (1978). "On the complexity of minimum spanning tree problems".
• [Garey and Johnson, 1979]: Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman.

[GiggleLiu]

Implemented in PR #999.