[Rule] HAMILTONIAN PATH to K-th SHORTEST PATH

[isPANN]

Source: HAMILTONIAN PATH
Target: K-th SHORTEST PATH
Motivation: Skipped — GJ specifies a Turing reduction (not a Karp/many-one reduction). Cannot be implemented as a single ReduceTo trait.
Reference: Garey & Johnson, Computers and Intractability, ND31, p.214

Note

This reduction is a Turing reduction (the target problem is used as an oracle multiple times), not a polynomial-time many-one (Karp) reduction. The GJ entry explicitly states "Turing reduction from HAMILTONIAN PATH" and notes the problem is "Not known to be in NP" (marked with *).

The codebase's ReduceTo<T> trait models Karp reductions (single transformation + solution extraction). A Turing reduction would require a different abstraction (oracle access pattern).

[isPANN]

Issue Quality Check — Rule

Re-check via /check-issue --force. No prior ## Issue Quality Check comment existed on this issue, so this is effectively the first run.

Check	Result	Details
Usefulness	⚠️ Warn	Target model KthShortestPath does not exist in the catalog and the issue is a deliberate skip notice, not a reduction proposal
Non-trivial	❌ Fail	No reduction algorithm provided — issue is a one-paragraph note explaining why GJ's construction cannot be implemented
Correctness	✅ Pass	Characterization of GJ ND31 (Turing reduction, problem marked * "not known to be in NP") matches the literature
Completeness	❌ Fail	GJ's cited construction has a precondition the codebase's ReduceTo<T> abstraction cannot satisfy: it is an oracle-call (Turing) reduction, not a many-one mapping — so it does not cover any full source instance under this trait
Well-written	❌ Fail	Required template sections (Reduction Algorithm, Size Overhead, Validation Method, Example) are absent by design

Overall: 1 passed, 3 failed, 1 warning

---

Usefulness

The target problem KthShortestPath (GJ ND31, K-TH SHORTEST PATH) is not in the catalog — pred show KthShortestPath returns Unknown problem, and there is no [Model] issue tracking it for implementation. The issue body explicitly states the reduction is skipped and not intended to land as code. It therefore does not propose an actionable new edge in the reduction graph.

A parallel precedent is #395 (PARTITION → KthLargestMTuple, GJ SP21), which was moved to OnHold for the same reason ("Not a Karp reduction" — see the tracking issue #1012, section "Not a Karp reduction (1)"). The natural resolution here is the same: park as OnHold (or close) rather than label Good.

Non-trivial

The issue contains no reduction algorithm — only a meta-note explaining why GJ's construction cannot be encoded as a ReduceTo<T> impl. There is no mapping, no gadget, no construction step, and no solution extraction to evaluate. Under the rubric's "Insufficient detail" clause this is a Fail.

Correctness

The claims in the body are verifiable against G&J Computers and Intractability (1979):

• ND31 K-TH SHORTEST PATH appears on p. 214 of the NP-hardness compendium.
• It is marked with *, which in G&J's notation means "not known to be in NP".
• The cited reduction from HAMILTONIAN PATH in the entry is explicitly described as a Turing reduction (oracle access to the K-th shortest path subroutine to detect the existence of a simple path of length |V|−1), not a many-one transformation.

So the literature characterization in the issue is accurate. Pass.

Completeness

This is the load-bearing check for this issue, and it fails:

• GJ's construction for ND31 is a Turing reduction: the source HAMILTONIAN PATH instance is decided by making multiple oracle queries to the K-TH SHORTEST PATH problem on derived instances. The codebase's ReduceTo<T> (and ReduceToAggregate<T>) traits model polynomial-time many-one (Karp) reductions — a single transformation Source -> Target plus a single solution-extraction map. There is no oracle / multi-query abstraction available.
• Consequently, the cited literature construction does not cover the full source HAMILTONIAN PATH problem under this codebase's reduction abstraction at all. It does not just fail on a corner case; it fails by construction on every instance, because the very shape of the reduction (multiple oracle calls + post-processing of their answers) cannot be expressed as a single Karp map.

This matches the rubric's Completeness verdict row "Literature has a precondition the issue ignores → Fail" — except here the precondition is the existence of an oracle/Turing-reduction abstraction, which the codebase explicitly does not provide. The fix the rubric offers ("add a preprocessing step that reduces the full source to the restricted variant") is not available, because there is no Karp construction in GJ to fall back on.

Note: fundamental_no_reference does not apply here — the cited paper (G&J, ND31, p. 214) genuinely contains the claimed (Turing) construction. The issue is that the construction is the wrong kind of reduction for this codebase, not that the reference is missing.

Well-written

Required [Rule] template sections that are absent:

• Reduction Algorithm (step-by-step procedure)
• Size Overhead (target metric formulas in terms of source size fields, e.g., num_vertices, num_edges)
• Validation Method
• Example (concrete worked instance)

These are absent by design because the issue is a skip notice, but under the literal [Rule] rubric this is a Fail. The motivation field is also effectively empty — it states why the rule is being skipped, not why this edge would be useful.

Recommendations

1. Resolution: mirror [Rule] PARTITION to K-th LARGEST m-TUPLE #395's handling — move this issue to OnHold (or close as wontfix), and record it under the "Not a Karp reduction" section of the skipped-rules tracking issue Tracking: skipped rules from low-tier reinspected derivations #1012. There is no actionable code change here.
2. If a Karp-style HamiltonianPath → KthShortestPath reduction is later wanted (e.g., via the second-shortest-path NP-hardness construction of Lalla, Krumke, and others, or via Eppstein's work on path enumeration), open a new [Rule] issue against a [Model] KthShortestPath that has actually been added, with a real construction. The current issue should not be re-purposed for that.
3. The codebase already exposes a Turing-reduction edge type (ReductionMode::Turing, see CLAUDE.md "Problem Variants" section), but it is only used today for P -> Decision<P> binary search. Generalizing it to multi-query oracle reductions would be a much larger design change than this issue can carry.

[isPANN]

auto-pipeline: parked on OnHold — G&J ND31 is a Turing reduction (multiple oracle calls to K-th Shortest Path), not Karp; not expressible under ReduceTo. Human triage needed (mirrors #395).