What is the Hamiltonian Path Problem?
Understand the Hamiltonian path problem, backtracking solutions, its NP-complete nature, and how to answer this graph interview question.
Expected Interview Answer
A Hamiltonian path is a path through a graph that visits every vertex exactly once, and finding one (or deciding one exists) is NP-complete in general, solved in practice with backtracking that extends a partial path one unvisited neighbor at a time and retreats when it gets stuck.
The algorithm keeps a partial path starting from some vertex, and at each step tries every unvisited neighbor of the last vertex added, recursing into that choice; if a branch cannot be extended to cover all remaining vertices, it backtracks and tries the next neighbor. A Hamiltonian cycle is the stricter version where the path must also return to its starting vertex, forming a closed loop. Because checking all permutations naively costs O(n!), practical solvers prune aggressively and only scale to modest graph sizes; larger instances rely on heuristics or are reformulated as other NP-hard problems like the traveling salesman problem. It is worth distinguishing from an Eulerian path, which visits every edge exactly once rather than every vertex — a subtly different and, notably, polynomial-time problem.
- Models any "visit every location exactly once" routing question
- Backtracking gives an exact answer for small-to-medium graphs
- Highlights the sharp contrast between vertex-covering (hard) and edge-covering (easy) path problems
- Foundational building block for understanding TSP and other NP-hard routing problems
AI Mentor Explanation
A cricket board wants a single tour where the team visits every host city exactly once before the season ends, never revisiting a city already played in. Planners build the tour city by city, only adding a city reachable from the current one by a direct connecting flight, and if the tour gets stuck with unreachable cities left, they backtrack and swap the last city for a different option. Whether such a complete, no-repeat tour exists at all is not obvious in advance and can require trying many partial itineraries before confirming one works or that none does. This is the essence of a Hamiltonian path: touching every city exactly once, not every possible flight route.
Step-by-Step Explanation
Step 1
Build a partial path
Start at a chosen vertex and maintain the sequence of visited vertices so far.
Step 2
Try an unvisited neighbor
Extend the path to any neighbor of the last vertex that has not yet been visited.
Step 3
Recurse and check completion
If the path now covers all vertices, a Hamiltonian path is found; otherwise keep extending.
Step 4
Backtrack on dead ends
If no unvisited neighbor extends the path successfully, remove the last vertex and try a different neighbor from the prior step.
What Interviewer Expects
- Define a Hamiltonian path as visiting every vertex exactly once
- Distinguish it from a Hamiltonian cycle (must return to start) and an Eulerian path (every edge once)
- Explain the backtracking approach and why naive search is O(n!)
- Acknowledge the problem is NP-complete in general
Common Mistakes
- Confusing Hamiltonian path (every vertex once) with Eulerian path (every edge once)
- Assuming every graph has a Hamiltonian path
- Forgetting that a Hamiltonian cycle additionally requires returning to the start vertex
- Not recognizing the NP-complete nature and defaulting to a polynomial-time claim
Best Answer (HR Friendly)
“A Hamiltonian path is a route through a graph that touches every point exactly once, without repeats. I think of it like planning a trip that visits every city on a list exactly once, and figuring out if such a route is even possible can be genuinely hard to compute as the list grows.”
Code Example
def hamiltonian_path(graph, vertices, path=None):
if path is None:
path = [vertices[0]]
if len(path) == len(vertices):
return path
last = path[-1]
for neighbor in graph[last]:
if neighbor not in path:
path.append(neighbor)
result = hamiltonian_path(graph, vertices, path)
if result is not None:
return result
path.pop()
return None
graph = {"A": ["B", "C"], "B": ["A", "C", "D"], "C": ["A", "B"], "D": ["B"]}
path = hamiltonian_path(graph, list(graph)) # e.g. ['A', 'C', 'B', 'D']Follow-up Questions
- How is the Hamiltonian cycle problem different from the Hamiltonian path problem?
- Why is finding an Eulerian path solvable in polynomial time while Hamiltonian path is not?
- How does the Hamiltonian cycle problem relate to the traveling salesman problem?
- What pruning strategies would speed up the backtracking search in practice?
MCQ Practice
1. What does a Hamiltonian path require?
A Hamiltonian path visits every vertex in the graph exactly once, with no repeats.
2. What additionally distinguishes a Hamiltonian cycle from a Hamiltonian path?
A Hamiltonian cycle is a Hamiltonian path with the added requirement that the last vertex connects back to the first.
3. Which problem is solvable in polynomial time, unlike the Hamiltonian path problem?
An Eulerian path (visiting every edge exactly once) can be found in linear time via a simple degree-parity condition, unlike the NP-complete Hamiltonian path.
Flash Cards
What does a Hamiltonian path visit exactly once? — Every vertex in the graph.
How does a Hamiltonian cycle differ from a Hamiltonian path? — A cycle must also return to the starting vertex.
What is the naive time complexity of checking all vertex orderings? — O(n!), since it tries all permutations of vertices.
What is a classic real-world instance of the Hamiltonian path problem? — The knight's tour on a chessboard.