[Model] DirectedHamiltonianPath

[isPANN]

Motivation

DIRECTED HAMILTONIAN PATH (P1) from Garey & Johnson, Chapter 3, p.60. A fundamental NP-complete graph problem: given a directed graph G = (V, A), does there exist a Hamiltonian path, i.e., an ordering of all vertices such that consecutive vertices in the ordering are connected by arcs? This is the directed counterpart of the undirected Hamiltonian Path problem, obtained by replacing each edge {u,v} with two arcs (u,v) and (v,u). NP-completeness follows directly from the undirected version.

Associated rules:

• R145: DIRECTED HAMILTONIAN PATH -> NO-WAIT FLOW-SHOP SCHEDULING (establishes NP-completeness of no-wait flow-shop)
• R194: DIRECTED HAMILTONIAN PATH -> SQUARE-TILING (establishes NP-completeness of bounded Wang tiling)

Definition

Name: DirectedHamiltonianPath

Canonical name: Directed Hamiltonian Path; also: Hamiltonian Path in Digraphs, D-HAM-PATH
Reference: Garey & Johnson, Computers and Intractability, Chapter 3, p.60

Mathematical definition:

INSTANCE: A directed graph G = (V, A), where V is a set of vertices and A is a set of ordered pairs of vertices (arcs).
QUESTION: Does G contain a Hamiltonian path, i.e., an ordering of V as <v_1, v_2, ..., v_n>, where n = |V|, such that (v_i, v_{i+1}) in A for 1 <= i < n?

This is a feasibility (decision) problem: the answer is yes or no.

Variables

• Count: n = |V| (one variable per vertex, representing its position in the path)
• Per-variable domain: {0, 1, ..., n-1} -- the position of vertex v in the Hamiltonian path ordering
• Meaning: pi(v) in {0, ..., n-1} assigns each vertex a unique position in the path. The path is valid iff for every consecutive pair (v at position i, w at position i+1), the arc (v, w) exists in A.

ILP alternative: n^2 binary variables x_{v,k} where x_{v,k} = 1 if vertex v occupies position k. Constraints: each vertex at exactly one position, each position has exactly one vertex, and consecutive positions must correspond to arcs in A.

Schema (data type)

Type name: DirectedHamiltonianPath
Variants: none (operates on a general directed graph)

Field	Type	Description
graph	DirectedGraph	The directed graph G = (V, A)

Notes:

• This is a feasibility (decision) problem: Value = Or (satisfiability-style).
• Key getter methods: num_vertices() (= |V|), num_arcs() (= |A|), delegated from the DirectedGraph field.
• The undirected HamiltonianPath is a special case: each undirected edge {u, v} corresponds to two arcs (u, v) and (v, u).

Complexity

• Decision complexity: NP-complete. The undirected Hamiltonian Path problem can be reduced to the directed version by replacing each edge {u,v} with arcs (u,v) and (v,u). NP-completeness follows from the undirected case (Karp, 1972 via Hamiltonian Circuit, then to path).
• Best known exact algorithm: O(n^2 * 2^n) time and O(n * 2^n) space via Held-Karp dynamic programming (Bellman, 1962; Held & Karp, 1962). The algorithm computes, for each subset S of vertices and endpoint v in S, whether there is a directed path visiting exactly the vertices in S and ending at v. Unlike the undirected case, no sub-2^n algorithm is known for directed Hamiltonian path.
• References:
  • R. Bellman (1962). "Dynamic programming treatment of the travelling salesman problem." J. ACM 9(1), pp. 61-63.
  • M. Held, R.M. Karp (1962). "A dynamic programming approach to sequencing problems." J. SIAM 10(1), pp. 196-210.

Specialization

• Generalization of: Hamiltonian Path (undirected) -- the undirected version is a special case where arcs come in symmetric pairs.
• Special case of: Directed Hamiltonian Circuit -- a Hamiltonian path is a Hamiltonian circuit minus one arc; standard reductions exist between the two (add a new vertex connected to all others).
• Known tractable cases: Tournaments (complete directed graphs) always have a Hamiltonian path (Ore, 1960); DAGs have a Hamiltonian path iff they have a unique topological ordering.

Extra Remark

Full book text:

All three Hamiltonian problems mentioned so far also remain NP-complete if we replace the undirected graph G by a directed graph and replace the undirected Hamiltonian circuit or path by a directed Hamiltonian circuit or path. Recall that a directed graph G = (V, A) consists of a vertex set V and a set of ordered pairs of vertices called arcs. A Hamiltonian path in a directed graph G = (V, A) is an ordering of V as <v_1, v_2, . . . , v_n>, where n = |V|, such that (v_i, v_{i+1}) ∈ A for 1 ≤ i < n. A Hamiltonian circuit has the additional requirement that (v_n, v_1) ∈ A. Each of the three undirected Hamiltonian problems can be transformed to its directed counterpart simply by replacing each edge {u, v} in the given undirected graph by the two arcs (u, v) and (v, u). In essence, the undirected versions are merely special cases of their directed counterparts.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all n! permutations of vertices; check if each consecutive pair has an arc.)
• It can be solved by reducing to integer programming. (ILP with binary variables x_{v,k} = 1 if vertex v is at position k; constraints: each vertex at exactly one position, each position has exactly one vertex, and for each consecutive position pair (k, k+1), the selected vertices must have an arc between them. Companion rule issue to be filed separately.)
• Other: Held-Karp DP in O(n^2 * 2^n).

Example Instance

Input:
G = (V, A) with V = {0, 1, 2, 3, 4, 5} (n = 6 vertices)
A = {(0,1), (0,3), (1,3), (1,4), (2,0), (2,4), (3,2), (3,5), (4,5), (5,1)}

Hamiltonian path: <0, 1, 3, 2, 4, 5>
Check: (0,1) in A, (1,3) in A, (3,2) in A, (2,4) in A, (4,5) in A. All 6 vertices visited exactly once.
Answer: YES.

Note: The path ordering is non-trivial -- vertex 3 must come before vertex 2 despite 2 < 3 in natural order. A greedy approach following (0,1), (1,4), ... would reach 4 -> 5 -> 1 and revisit vertex 1, failing. The correct path requires backtracking from vertex 1 to vertex 3 rather than vertex 4.

Negative example:
Remove arcs (3,2) and (5,1) from the positive example.
G' = (V, A') with A' = {(0,1), (0,3), (1,3), (1,4), (2,0), (2,4), (3,5), (4,5)}.

Vertex 2 has no incoming arcs in G', so any Hamiltonian path must start at vertex 2. From vertex 2, the only outgoing arcs lead to 0 or 4:

• 2→0→1→3→5→? (must reach 4, but no arc from 5 to 4)
• 2→0→1→4→5→? (must reach 3, but no arc from 5 to 3)
• 2→0→3→5→? (must reach 1 and 4, but no outgoing arcs from 5 to either)
• 2→4→5→? (no outgoing arcs from 5 to unvisited vertices)
  Exhaustive search confirms no directed Hamiltonian path exists. Answer: NO.

Python validation script

from itertools import permutations

def find_ham_paths(n, arcs):
    arc_set = set(arcs)
    paths = []
    for perm in permutations(range(n)):
        if all((perm[i], perm[i+1]) in arc_set for i in range(n-1)):
            paths.append(list(perm))
    return paths

# Positive example
arcs_pos = [(0,1),(0,3),(1,3),(1,4),(2,0),(2,4),(3,2),(3,5),(4,5),(5,1)]
paths_pos = find_ham_paths(6, arcs_pos)
assert [0,1,3,2,4,5] in paths_pos
assert len(paths_pos) == 5
print(f"Positive: {len(paths_pos)} Hamiltonian paths")

# Negative example
arcs_neg = [(0,1),(0,3),(1,3),(1,4),(2,0),(2,4),(3,5),(4,5)]
paths_neg = find_ham_paths(6, arcs_neg)
assert len(paths_neg) == 0
print("Negative: No Hamiltonian path (correct)")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but ILP companion issue not linked
Non-trivial	✅ Pass	Distinct from undirected HamiltonianPath — directed arcs change feasibility constraints
Correctness	❌ Fail	Complexity claim wrong; negative example invalid
Well-written	❌ Fail	Missing ILP companion link; broken negative example

Overall: 1 passed, 1 warning, 2 failed

---

Usefulness

The problem DirectedHamiltonianPath does not exist in the codebase. The undirected HamiltonianPath and HamiltonianCircuit exist, but no directed counterparts. The issue mentions two planned reductions (R145: DHP -> No-Wait Flow-Shop Scheduling, R194: DHP -> Square-Tiling), which provide graph connectivity.

However, the "How to solve" section checks the ILP box, claiming direct ILP solvability with a concrete ILP formulation. Per project conventions, this requires a companion [Rule] DirectedHamiltonianPath to ILP issue to be linked in the issue body. No such companion issue exists or is referenced. Warn — this must be addressed before implementation.

Non-trivial

DirectedHamiltonianPath operates on directed graphs with arcs (ordered pairs), while the existing HamiltonianPath operates on undirected graphs with edges. The feasibility constraint requires consecutive vertices in the ordering to be connected by a directed arc, not merely an edge. This is a genuinely distinct problem — the undirected version is a strict special case (symmetric arc pairs). Pass.

Correctness

3a — Definition: The formal definition is correct and matches Garey & Johnson p.60.

3b — Complexity (FAIL):

The issue claims Bjorklund (2010) provides an O*(1.657^n) randomized algorithm for directed Hamiltonian path. This is incorrect. Bjorklund's "Determinant Sums for Undirected Hamiltonicity" (FOCS 2010) applies only to undirected graphs. The title of the paper itself says "Undirected." For directed graphs, no algorithm breaking the O*(2^n) barrier is known. The best known exact algorithm for directed Hamiltonian path remains Held-Karp DP at O(n^2 * 2^n).

The issue also claims O*(1.415^n) for bipartite digraphs and O*(1.619^n) parity computation — these likewise apply to undirected graphs only.

The correct complexity entry for declare_variants! should be "num_vertices^2 * 2^num_vertices" (Held-Karp), not anything based on 1.657.

3c — References: The Bellman (1962) and Held-Karp (1962) references are real and correctly cited. heldkarp1962 is already in the project bibliography. The Bjorklund (2010) and Bjorklund-Husfeldt (2013) papers are real but misapplied to the directed case.

3d — Negative example (FAIL):

The negative example claims that removing arcs (3,2) and (2,4) makes the graph have no Hamiltonian path. This is false. The path (2, 0, 3, 5, 1, 4) is a valid Hamiltonian path in the modified graph:

• (2,0) in A ✓, (0,3) in A ✓, (3,5) in A ✓, (5,1) in A ✓, (1,4) in A ✓

Well-written

4a — Information Completeness:

Section	Status
Motivation	✅ Present with concrete G&J reference and planned reductions
Name	✅ DirectedHamiltonianPath — follows conventions
Reference	✅ Garey & Johnson p.60
Definition	✅ Formal INSTANCE/QUESTION format
Variables	✅ Count, domain, meaning described
Schema	⚠️ Proposes raw vertices/arcs fields; should consider using existing DirectedGraph type (see D2CIF)
Complexity	❌ Wrong claims (see Correctness)
How to solve	❌ ILP checked but no companion [Rule] DirectedHamiltonianPath to ILP issue linked
Example Instance	✅ Positive example is correct and non-trivial (5 valid paths out of 720 permutations)
Negative Example	❌ Incorrect — a Hamiltonian path exists in the "negative" instance

4b — Definition Completeness: The formal definition is clear and implementable.

4c — Symbol Consistency: Symbols are consistent across sections (V, A, n used uniformly).

4d — Example Quality: The positive example is good (6 vertices, 10 arcs, 5 Hamiltonian paths — non-trivial). The negative example is broken and must be replaced.

Recommendations

• Fix the complexity section: remove all Bjorklund claims for the directed case. The best known is Held-Karp O(n^2 * 2^n). If you want to mention Bjorklund, note it applies only to the undirected variant.
• Fix or replace the negative example with one that genuinely has no Hamiltonian path.
• Consider using DirectedGraph type in the schema for consistency with DirectedTwoCommodityIntegralFlow.
• File a companion [Rule] DirectedHamiltonianPath to ILP issue, or uncheck the ILP box and describe ILP solvability as indirect (via reduction chain).

[isPANN]

Fix-issue changelog

• Complexity section: Removed incorrect Bjorklund O*(1.657^n) claim — that algorithm applies only to undirected graphs. Best known for directed remains Held-Karp O(n²·2^n). Also removed bipartite O*(1.415^n) and parity O*(1.619^n) claims.
• Negative example: Replaced broken example (removing arcs (3,2) and (2,4) still left path [2,0,3,5,1,4]) with correct one (remove arcs (3,2) and (5,1) — verified 0 Hamiltonian paths by exhaustive search).
• Schema: Changed from raw vertices/arcs fields to graph: DirectedGraph, consistent with existing directed graph models (MinimumFeedbackArcSet, IntegralFlowHomologousArcs, etc.).
• ILP note: Added clarification that companion [Rule] DirectedHamiltonianPath to ILP issue will be filed separately.
• Added Python validation script in collapsible section verifying both positive (5 paths) and negative (0 paths) examples.

Applied by /fix-issue.