[Model] HamiltonianPathBetweenTwoVertices

[isPANN]

Motivation

HAMILTONIAN PATH BETWEEN TWO POINTS (P2) from Garey & Johnson, Chapter 3, p.60. A classical NP-complete problem useful for reductions. It serves as the source problem for establishing NP-completeness of LONGEST PATH (ND29 in G&J) and is itself derived from HAMILTONIAN PATH by fixing the two endpoints.

Definition

Name: HamiltonianPathBetweenTwoVertices
Canonical name: HAMILTONIAN PATH BETWEEN TWO POINTS
Reference: Garey & Johnson, Computers and Intractability, Chapter 3, p.60

Mathematical definition:

INSTANCE: Graph G = (V, E), two distinguished vertices s, t in V.
QUESTION: Does G contain a Hamiltonian path from s to t, i.e., a simple path that visits every vertex exactly once and begins at s and ends at t?

Variables

• Count: n = |V| variables, interpreted as a permutation encoding.
• Per-variable domain: Position index in {0, 1, ..., n-1}. Each position holds a vertex index.
• Meaning: The variable assignment encodes a vertex ordering (permutation) pi such that pi(0) = s, pi(n-1) = t, and {pi(i), pi(i+1)} in E for all i = 0, ..., n-2. A satisfying assignment is a Hamiltonian s-t path.

Schema (data type)

Type name: HamiltonianPathBetweenTwoVertices
Variants: graph topology (graph type parameter G)

Field	Type	Description
graph	SimpleGraph	The undirected graph G=(V,E)
source_vertex	usize	Distinguished source vertex s
target_vertex	usize	Distinguished target vertex t

Notes:

• This is a satisfaction (decision) problem: Value = Or.
• No weight type is needed.
• Generalizes to directed graphs (also NP-complete per G&J).

Complexity

• Best known exact algorithm: 1.657^num_vertices — randomized time via Bjorklund's "Determinant Sums" Monte Carlo algorithm (2010/2014), same as for general Hamiltonian Path and Hamiltonian Circuit. For bipartite graphs: O*(1.415^n).
• Classic algorithm: O(n^2 * 2^n) deterministic dynamic programming (Bellman 1962, Held-Karp 1962) — the DP state (current vertex, visited subset) naturally handles fixed endpoints by initializing only from s and accepting only at t.
• NP-completeness: NP-complete (Garey & Johnson, Section 3.1.4, p.60; via modification of the VC -> HC construction).
• References:
  • M. Held and R.M. Karp (1962). "A dynamic programming approach to sequencing problems." Journal of the Society for Industrial and Applied Mathematics, 10(1):196-210.
  • A. Bjorklund (2014). "Determinant Sums for Undirected Hamiltonicity." SIAM Journal on Computing, 43(1):280-299.

Extra Remark

Full book text:

HAMILTONIAN PATH BETWEEN TWO POINTS is the same as HAMILTONIAN PATH, except that two vertices u and v are specified as part of each instance, and we are asked whether G contains a Hamiltonian path beginning with u and ending with v.

How to solve

• It can be solved by (existing) bruteforce — enumerate all permutations of vertices starting at s and ending at t, check if consecutive pairs are edges.
• It can be solved by reducing to integer programming.
• Other: Held-Karp DP in O(n^2 * 2^n) time with fixed endpoints; Bjorklund's randomized algorithm in O*(1.657^n). Also reducible to HamiltonianPath (trivially, since any s-t Hamiltonian path is a Hamiltonian path) and to LongestPath (ND29 in G&J, set K = |V|-1).

Example Instance

Instance 1 (has Hamiltonian s-t path, non-trivial routing):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5}, s=0, t=5, and 8 edges:

• Edges: {0,1}, {0,3}, {1,2}, {1,4}, {2,5}, {3,4}, {4,5}, {2,3}
• Hamiltonian s-t path: 0 -> 3 -> 2 -> 1 -> 4 -> 5
  • Check: {0,3} yes, {3,2} yes, {2,1} yes, {1,4} yes, {4,5} yes
• Note: The greedy path 0 -> 1 -> 2 -> 5 gets stuck (only 4 vertices visited). The correct path requires the non-obvious start 0 -> 3.
• Answer: YES

Instance 2 (no Hamiltonian s-t path despite graph being Hamiltonian):
Graph G with 5 vertices {0, 1, 2, 3, 4}, s=0, t=2, and 5 edges:

• Edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,0}
• (This is a 5-cycle C_5)
• A Hamiltonian path exists: 0 -> 1 -> 2 -> 3 -> 4
• But the only Hamiltonian s-t path (s=0, t=2) would need to visit all 5 vertices starting at 0 and ending at 2. The two paths from 0 are: 0->1->2 (only 3 vertices) or 0->4->3->2 (only 4 vertices). Neither visits all 5 vertices.
• Answer: NO

Expected Outcome

Instance 1: YES — a Hamiltonian s-t path exists. One valid solution: 0 → 3 → 2 → 1 → 4 → 5. There are 4 distinct Hamiltonian s-t paths total (verified by exhaustive enumeration), making this a good round-trip test instance.

Instance 2: NO — no Hamiltonian s-t path exists. All 6 middle-vertex permutations fail to produce a valid path (verified by exhaustive enumeration).

Python validation script

from itertools import permutations

def find_hamiltonian_st_paths(n, edges, s, t):
    edge_set = set()
    for u, v in edges:
        edge_set.add((u, v))
        edge_set.add((v, u))
    middle = [v for v in range(n) if v != s and v != t]
    paths = []
    for perm in permutations(middle):
        path = [s] + list(perm) + [t]
        if all((path[i], path[i+1]) in edge_set for i in range(len(path)-1)):
            paths.append(path)
    return paths

# Instance 1: 6 vertices, s=0, t=5
edges1 = [(0,1),(0,3),(1,2),(1,4),(2,5),(3,4),(4,5),(2,3)]
paths1 = find_hamiltonian_st_paths(6, edges1, 0, 5)
assert [0,3,2,1,4,5] in paths1
assert len(paths1) == 4
print(f"Instance 1: {len(paths1)} Hamiltonian s-t paths found")

# Instance 2: C_5, s=0, t=2
edges2 = [(0,1),(1,2),(2,3),(3,4),(4,0)]
paths2 = find_hamiltonian_st_paths(5, edges2, 0, 2)
assert len(paths2) == 0
print("Instance 2: No Hamiltonian s-t path (correct)")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem; planned reductions to HamiltonianPath and LongestPath
Non-trivial	✅ Pass	Distinct feasibility constraint (fixed endpoints s, t) from HamiltonianPath
Correctness	✅ Pass	Both references verified in project bibliography; complexity claims consistent
Well-written	⚠️ Warn	Minor structural issues (see details below)

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

• Problem HamiltonianPathBetweenTwoVertices does not exist in the codebase.
• The issue mentions planned connections: reducible to HamiltonianPath (trivially) and to LongestPath (set K = |V|−1). These connect it to the existing reduction graph.
• Motivation is concrete: classical G&J problem (p.60), serves as source for LongestPath NP-completeness.
• No ILP path claimed, so no ILP crossref required.

Non-trivial

• HamiltonianPath exists but has only a graph field — no endpoint parameters. This proposed problem adds source and target vertices as structural fields with a genuinely different feasibility constraint (path must start at s, end at t).
• Not isomorphic to any existing problem. LongestPath has source_vertex/target_vertex but is an optimization problem with weighted edges — structurally different.

Correctness

References verified:

• Bjorklund 2014 "Determinant Sums for Undirected Hamiltonicity" — present in docs/paper/references.bib as bjorklund2014. SIAM J. Comput. 43(1):280–299. The O*(1.657^n) randomized bound applies to the fixed-endpoint variant via standard reduction (add auxiliary vertex connected to s and t, check Hamiltonian cycle).
• Held & Karp 1962 "A Dynamic Programming Approach to Sequencing Problems" — present as heldkarp1962. J. SIAM 10(1):196–210. O(n² · 2^n) deterministic DP is correct and naturally handles fixed endpoints.
• G&J p.60 Section 3.1.4 — standard reference for NP-completeness of this problem.

Complexity claims check out. The 1.657^num_vertices expression used by the existing HamiltonianPath and HamiltonianCircuit problems in the codebase is consistent with the issue's claim.

Examples verified by exhaustive enumeration:

• Instance 1 (6 vertices, s=0, t=5): ✅ Hamiltonian path 0→3→2→1→4→5 confirmed. 4 total Hamiltonian s-t paths found (good diversity for testing). Greedy path 0→1→2→5 confirmed to get stuck (misses vertices 3, 4).
• Instance 2 (C₅, s=0, t=2): ✅ No Hamiltonian s-t path exists, confirmed by checking all 6 permutations.

Well-written

Present and substantive: Motivation, Definition, Variables, Schema, Complexity, How to solve, Example Instance — all present with meaningful content.

Warnings:

1. No dedicated "Expected Outcome" section. The outcomes (YES/NO with paths) are embedded in the Example Instance section. For template compliance, consider adding a separate "Expected Outcome" heading.

2. ⚠️ Unverified markers appear throughout the issue (Definition, Variables, Schema, Complexity, Example). These should be removed after the content has been verified (which this check has now done).

3. "R50" reference in motivation ("LONGEST PATH (R50, ND29)") — this appears to be an internal rule numbering that doesn't correspond to an actual [Rule] issue. Consider replacing with a link to a concrete [Rule] issue or removing the reference.

4. Schema field naming consistency. The issue proposes source and target as field names. The existing LongestPath problem uses source_vertex and target_vertex. Consider aligning field names for consistency across the codebase.

5. Complexity expression format. Should provide a concrete expression like 1.657^num_vertices (matching codebase convention) rather than "O*(1.657^n)".

Recommendations

• The examples are good quality — 4 distinct Hamiltonian paths in Instance 1 and a clean negative instance in Instance 2 provide excellent round-trip test material.
• Consider noting the standard reduction from HamiltonianPathBetweenTwoVertices to HamiltonianCircuit (add edge s-t, check for HC) as a potential future [Rule] issue.

[isPANN]

Fix-issue changelog

• Removed all 5 ⚠️ Unverified markers (content verified by check-issue + Python exhaustive enumeration)
• Renamed schema fields source/target → source_vertex/target_vertex to match LongestPath convention
• Added dedicated "Expected Outcome" section with Python validation script
• Fixed complexity expression format: 1.657^num_vertices (codebase convention)
• Replaced invented "R50" rule reference with "ND29 in G&J"

Applied by /fix-issue.

[isPANN]

Please kindly check the following items (PR #960):

• Paper (PDF): check definition, proof sketch, example figure, and reproducible pred commands
• Implementation (Optional): spot-check the source files changed in this PR for correctness

💬 Join the discussion on Zulip — feel free to ask questions or leave feedback there.