[Rule] HAMILTONIAN PATH to KTH BEST SPANNING TREE

[isPANN]

---

name: Rule
about: Propose a new reduction rule
title: "[Rule] HAMILTONIAN PATH to KTH BEST SPANNING TREE"
labels: rule
assignees: ''
canonical_source_name: 'Hamiltonian Path'
canonical_target_name: 'Kth Best Spanning Tree'
source_in_codebase: false
target_in_codebase: false

Source: HAMILTONIAN PATH
Target: KTH BEST SPANNING TREE
Motivation: Establishes NP-hardness of KTH BEST SPANNING TREE via Turing reduction from HAMILTONIAN PATH. Unlike most reductions in Garey & Johnson which are Karp (many-one) reductions, this is a Turing reduction, and the problem is marked with (*) indicating it is not known to be in NP. The problem can be solved in pseudo-polynomial time via Lawler's K-best enumeration procedure (1972), and is polynomial for any fixed K, but becomes NP-hard when K is part of the input.

Reference: Garey & Johnson, Computers and Intractability, ND9, p.208

GJ Source Entry

[ND9] K^th BEST SPANNING TREE (*)
INSTANCE: Graph G=(V,E), weight w(e) in Z_0^+ for each e in E, positive integers K and B.
QUESTION: Are there K distinct spanning trees for G, each having total weight B or less?
Reference: [Johnson and Kashdan, 1976]. Turing reduction from HAMILTONIAN PATH.
Comment: Not known to be in NP. Can be solved in pseudo-polynomial time (polynomial in |V|, K, log B, max{log w(e): e in E}) [Lawler, 1972], and hence in polynomial time for any fixed value of K. The corresponding enumeration problem is #P-complete. However, the unweighted case of the enumeration problem is solvable in polynomial time (e.g., see [Harary and Palmer, 1973]).

Reduction Algorithm

Summary:
This is a Turing reduction (not a many-one/Karp reduction), meaning it uses an oracle for KTH BEST SPANNING TREE to solve HAMILTONIAN PATH. Given a HAMILTONIAN PATH instance G = (V, E) with n = |V| vertices, the reduction proceeds as follows:

1. Weight assignment: Assign weight w(e) = 0 to every edge e in E. Alternatively, assign weight 1 to every edge (all spanning trees then have weight exactly n-1).

2. Oracle usage (Turing reduction): The key insight is that a Hamiltonian path in G is a spanning tree with maximum degree 2 (i.e., a path). The reduction uses the KTH BEST SPANNING TREE oracle to enumerate spanning trees in order of weight, checking each one to see if it is a Hamiltonian path.

3. Specific construction (unit weights): Set w(e) = 1 for all e in E, set B = n - 1 (every spanning tree has exactly n - 1 edges, so weight = n - 1), and vary K. Ask: "Are there K distinct spanning trees of weight at most n - 1?" By binary search on K, determine the total number of spanning trees. Then enumerate them (using Lawler's procedure with the oracle) and check if any is a path.

4. Alternative construction (Hamiltonian path detection): Assign non-uniform weights to distinguish Hamiltonian paths from other spanning trees:

   • Assign w(e) = 0 for all e in E.
   • Set B = 0 and K = 1: "Is there at least 1 spanning tree of weight 0?" (Always yes if G is connected.)
   • The Turing reduction adaptively queries the oracle to enumerate all minimum-weight spanning trees and tests each for the path property.

5. Solution extraction: Among the enumerated spanning trees, a Hamiltonian path is one where every vertex has degree at most 2 in the tree.

Note: Because this is a Turing reduction rather than a Karp reduction, the problem is marked (*) in G&J, indicating it is not known to be in NP. The certificate for "K distinct spanning trees of weight <= B" would require listing K spanning trees, which may take exponential space in K.

Source: Johnson and Kashdan (1976); Lawler (1972), "A procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem", Management Science 18, pp. 401-405.

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 (unchanged)
num_edges	num_edges (unchanged)
K	varies (Turing reduction makes multiple queries)
B	num_vertices - 1 (with unit weights)

Derivation: The graph structure is unchanged in each oracle query. The weight function is trivially assigned (unit or zero weights). The overhead is in the number of oracle calls, not in the size of a single instance. With Lawler's procedure, up to O(n * tau(G)) oracle calls may be needed, where tau(G) is the number of spanning trees of G.

Validation Method

• Since this is a Turing reduction, standard closed-loop testing is more complex. The validation approach:
  1. Construct a graph G with a known Hamiltonian path.
  2. Enumerate spanning trees of G using Lawler/Eppstein K-best enumeration.
  3. Verify that at least one spanning tree has maximum degree 2 (is a Hamiltonian path).
  4. Construct a graph G' with NO Hamiltonian path and verify no spanning tree is a path.
• For the decision version with specific (K, B): verify that the answer is consistent with the number of spanning trees of weight <= B.
• Compare the number of spanning trees (Kirchhoff's matrix tree theorem) with the oracle answers.

Example

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

• Edges: {0,1}, {0,2}, {1,2}, {1,3}, {2,4}, {3,4}, {3,5}, {4,5}, {0,5}
• Hamiltonian path exists: 0 -- 1 -- 3 -- 5 -- 4 -- 2
  • Check: {0,1} YES, {1,3} YES, {3,5} YES, {5,4} YES, {4,2} YES. All vertices visited.

Constructed target instance (Kth Best Spanning Tree):

• Graph: G with unit weights w(e) = 1 for all edges.
• B = 5 (= n - 1 = 6 - 1; every spanning tree has weight 5).
• K = 1 (first query: is there at least 1 spanning tree of weight <= 5? Yes, G is connected).

Turing reduction queries:
Query the oracle to enumerate spanning trees:

1. 1st best spanning tree: Some minimum spanning tree (all have weight 5 since all edges have weight 1). E.g., {0,1}, {1,2}, {1,3}, {3,5}, {4,5} -- degrees: 0:1, 1:3, 2:1, 3:2, 4:1, 5:2. Max degree = 3. Not a Hamiltonian path.
2. 2nd best: Another spanning tree, e.g., {0,1}, {1,2}, {2,4}, {4,3}, {3,5}. Degrees: 0:1, 1:2, 2:2, 3:2, 4:2, 5:1. Max degree = 2. This IS a Hamiltonian path: 0--1--2--4--3--5. FOUND.

Solution extraction:

• The spanning tree {0,1}, {1,2}, {2,4}, {4,3}, {3,5} has all vertices with degree <= 2.
• Reading the path: 0 -- 1 -- 2 -- 4 -- 3 -- 5.
• Verify in G: {0,1} YES, {1,2} YES, {2,4} YES, {4,3} = {3,4} YES, {3,5} YES. Valid.
• Hamiltonian path found.

Contrast with non-Hamiltonian graph:
Graph H with 6 vertices {0,1,2,3,4,5} and edges forming K_{1,5} (star): {0,1}, {0,2}, {0,3}, {0,4}, {0,5}.

• The only spanning tree is the star itself (the graph is a tree).
• K = 1, B = 5: YES (1 spanning tree of weight 5).
• But vertex 0 has degree 5, so this is not a Hamiltonian path.
• No further spanning trees exist, so no Hamiltonian path in H.

References

• [Johnson and Kashdan, 1976]: [Johnson1976a] David B. Johnson and S. D. Kashdan (1976). "Lower bounds for selection in $X+Y$ and other multisets". Computer Science Department, Pennsylvania State University.
• [Lawler, 1972]: [Lawler1972] Eugene L. Lawler (1972). "A procedure for computing the {$K$} best solutions to discrete optimization problems and its application to the shortest path problem". Management Science 18, pp. 401-405.
• [Harary and Palmer, 1973]: [Harary1973] F. Harary and E. M. Palmer (1973). "Graphical Enumeration". Academic Press, New York.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	❌ Fail	Turing reduction — incompatible with codebase ReduceTo trait (Karp reductions only)
Non-trivial	❌ Fail	No structural transformation: graph is passed unchanged; reduction logic is entirely in oracle interaction
Correctness	⚠️ Warn	Lawler (1972) and Harary & Palmer (1973) verified; Johnson & Kashdan (1976) reference has title/content mismatch
Well-written	❌ Fail	Overhead table has invalid entry (K = "varies"); algorithm lacks implementable steps for Karp reduction

Overall: 0 passed, 3 failed, 1 warning

---

Usefulness

This reduction cannot be implemented in the current codebase. The ReduceTo<T> trait (in src/rules/traits.rs) implements Karp (many-one) reductions: a single call to reduce_to() produces one target problem instance, and extract_solution() maps a target solution back to a source solution. This is the fundamental building block of the entire reduction graph.

A Turing reduction (as described in this issue and in Garey & Johnson ND9) requires an oracle for the target problem that is called multiple times adaptively — the next query depends on the answer to the previous query. This is architecturally incompatible with the ReduceTo trait. The issue itself acknowledges this: "The overhead is in the number of oracle calls, not in the size of a single instance."

Neither Hamiltonian Path nor Kth Best Spanning Tree exists in the codebase, and even if they did, a Turing reduction between them cannot be expressed as a ReduceTo implementation.

Non-trivial

The "reduction" does not perform any structural transformation of the problem instance:

• The graph G = (V, E) is passed unchanged to the target problem.
• The only modification is assigning unit weights w(e) = 1 to all edges — this is trivial weight assignment, not a structural transformation.
• The actual computational content (enumerating spanning trees and checking degree constraints) lives entirely in the oracle interaction pattern, which cannot be captured by a single reduce_to() call.

In a proper Karp reduction, the source instance is transformed into a structurally different target instance (e.g., adding gadgets, penalty terms, auxiliary variables). Here, the "transformation" is identity on the graph structure.

Correctness

Lawler (1972): ✅ Verified. "A procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem," Management Science 18(7):401-405. The paper exists and describes the K-best enumeration procedure as claimed.

Harary and Palmer (1973): ✅ Verified. "Graphical Enumeration," Academic Press, New York. Confirmed as a standard reference on graph enumeration.

Johnson and Kashdan (1976): ⚠️ The issue cites this as a 1976 technical report from Pennsylvania State University titled "Lower bounds for selection in X+Y and other multisets." However, the published version (Johnson and Kashdan, JACM 25(4):556-570, 1978) is about selection in multisets — it is not obvious that this paper contains the Turing reduction from Hamiltonian Path to Kth Best Spanning Tree. The G&J entry cites "[Johnson and Kashdan, 1976]" for the ND9 problem definition, but the paper's actual content (lower bounds for selection) does not obviously cover spanning tree enumeration hardness. This may be a different Johnson & Kashdan paper, or the citation in G&J may refer to a different result in the same report. Cannot verify the specific claim.

Garey & Johnson ND9: The quoted entry is consistent with the book's style and known content. The (*) marking for "not known to be in NP" and the Turing reduction attribution are consistent with how G&J handles such problems.

Well-written

Overhead Table: The entry K = varies (Turing reduction makes multiple queries) is not a valid overhead expression. All overhead entries must be polynomial expressions in terms of source problem metrics (e.g., num_vertices, num_edges). Since this is a Turing reduction, a single-instance overhead table is fundamentally ill-defined — further evidence this reduction type is incompatible with the codebase.

Algorithm Completeness: The algorithm section describes a high-level strategy ("enumerate spanning trees, check if any is a path") but does not provide a step-by-step procedure that could be implemented as a reduce_to() method. Steps like "binary search on K" and "adaptively queries the oracle" are Turing reduction mechanics, not Karp reduction construction steps.

Symbol Consistency: The symbols n, m, K, B, and tau(G) are used but tau(G) (number of spanning trees) is introduced only in the derivation section without prior definition.

Example: The example is reasonably well-constructed and demonstrates the Turing reduction concept clearly. However, it illustrates an oracle-based enumeration process, not a single-instance Karp reduction — reinforcing that this cannot be implemented.

Recommendations

• This issue describes a historically important and mathematically correct result, but it is not suitable for implementation in this codebase due to the Turing vs. Karp reduction distinction.
• If the goal is to add Hamiltonian Path problems to the codebase, consider instead a Karp reduction such as: Hamiltonian Path → Hamiltonian Cycle (add a universal vertex), or 3-SAT → Hamiltonian Path (the classic Garey-Johnson-Tarjan construction).
• If the goal is to add spanning tree problems, consider Karp reductions involving degree-constrained spanning trees or minimum spanning tree variants that admit many-one reductions.