Certificate = a vertex sequence; verifier checks length, distinctness, edges.
CLO-3R2·30 ptsL10
🔊 Listen
1 · HAMPATH, formally
HAMPATH = {⟨G, s, t⟩ : G is a directed graph containing a Hamiltonian path from s to t}. A Hamiltonian path visits every vertex exactly once. Finding one in general graphs is famously hard — but verifying one is easy. This asymmetry is the textbook NP example.
The verifier · what to check, in what order
Given input (G, s, t) plus certificate π = v1 v2 … vn:
Length check: |π| = n (every vertex appears exactly once).
Distinctness check: vi ≠ vj for all i ≠ j (no repeats).
Endpoint check: v1 = s and vn = t.
Edge check: for each adjacent pair (vi, vi+1), there is an edge in G.
Time: O(n²) (or O(n) with a hash set). HAMPATH ∈ NP.
HAMPATH is NP-complete (Karp 1972). 3SAT reduces to HAMPATH via a clever gadget construction — see Sipser §7.5.
2 · The four checks visualised
🔊 Listen
3 · Animated demo · auto-plays · loops
Step through verification of a candidate path Auto-plays
4 · Pitfalls
"Visits every vertex" is the strong constraint. Don't confuse with "PATH" (just s-to-t reachability, in P). HAMPATH requires the path to be Hamiltonian — every vertex used exactly once.
Directed vs undirected matters. Sipser's HAMPATH is directed. The undirected version is equally NP-complete but the reduction proofs differ.
The certificate is the path, not the existence claim. Hand the verifier the explicit vertex sequence; it then checks. Don't conflate "there exists a path" (the question) with "here is a path" (the certificate).
Brute force is n!, not 2ⁿ. Try every permutation of vertices. For n = 20: 2.4 × 10¹⁸ permutations. Worse than 2ⁿ for small n.
🔊 Listen
5 · Q&A defence notes
Q1. Why O(n²)?
For n vertices: length check O(n), distinctness check O(n²) with naive comparison (or O(n) with a hash set), endpoint check O(1), edge checks O(n) lookups in adjacency matrix. Total: O(n²).
Q2. Why is finding a Hamiltonian path hard?
Brute force tries up to n! orderings. No polynomial-time algorithm is known; HAMPATH is NP-complete (3SAT reduces to it via gadgets). Even approximation is hard.
Q3. What's the certificate size?
n vertex labels, each O(log n) bits → total O(n log n) bits. Polynomial in input size, satisfying NP's certificate-length requirement.
Q4. How does HAMPATH compare to TSP?
TSP (traveling salesman) is HAMPATH plus weights — find a Hamiltonian cycle of minimum total weight. TSP-decision (cost ≤ k?) is also NP-complete. HAMPATH is the unweighted special case.