Hamiltonian Path Problem: Complexity Analysis and Applications

Introduction and Core Concepts

The hamiltonian path problem is one of the most fundamental and intensively studied problems in graph theory and theoretical computer science. Formally, given an undirected or directed graph G = (V, E), a Hamiltonian path is a path that visits each vertex in V exactly once. The decision version of the problem asks whether such a path exists, while the search version requires actually constructing the path if it exists. Unlike paths that may reuse vertices or simply seek the shortest route, the Hamiltonian path imposes a strict global constraint: complete and non-repetitive coverage of all vertices.

The problem is named after the Irish mathematician Sir William Rowan Hamilton, who in 1857 invented the Icosian game — a puzzle that challenged players to find a Hamiltonian cycle on the edges of a dodecahedron. While the game itself was recreational, it captured a deep combinatorial property that would later become central to complexity theory. The hamiltonian path problem is closely related to the Hamiltonian cycle problem, which requires the path to start and end at the same vertex, forming a cycle. A Hamiltonian cycle can be reduced to a Hamiltonian path by splitting a vertex, and vice versa, making the two problems computationally equivalent.

Why does the hamiltonian path problem matter? First, it was one of Karp's original 21 NP-complete problems, meaning it serves as a benchmark for computational hardness. No known polynomial-time algorithm exists for general graphs, and discovering one would imply P = NP, solving the most important open question in computer science. Second, it models numerous real-world scenarios where an entity must visit a set of locations exactly once without repetition, from genome assembly to circuit board drilling and delivery routing. Understanding its complexity helps engineers decide when to seek exact solutions, approximation algorithms, or heuristics. For students and practitioners of graph algorithms, mastering this problem builds intuition for backtracking, dynamic programming over subsets, and reduction techniques that apply far beyond this single problem.

Hamiltonian Path vs. Related Path Concepts

It is crucial to distinguish a Hamiltonian path from an Eulerian path, a common source of confusion. An Eulerian path visits every edge exactly once, while a Hamiltonian path visits every vertex exactly once. Euler's theorem provides a simple, linear-time characterization for Eulerian paths based on vertex degrees, whereas no such simple characterization is known for Hamiltonian paths. This contrast perfectly illustrates the gap between problems in P and NP-complete problems: superficially similar definitions can lead to vastly different computational complexities.

Another related concept is the Traveling Salesperson Problem (TSP). TSP seeks the shortest Hamiltonian cycle in a weighted complete graph. If we could solve the hamiltonian path problem efficiently, we could also solve TSP efficiently, but the converse is not true without additional constraints. This relationship makes Hamiltonian path a foundational subproblem for optimization variants.

How It Works

At its core, solving the hamiltonian path problem requires exploring the exponentially large space of vertex permutations. For a graph with n vertices, there are n! possible orderings. A naive brute-force approach would generate each permutation and check whether consecutive vertices in the permutation are connected by an edge in the graph. While correct, this is computationally infeasible for n greater than about 12.

The most intuitive improvement is backtracking via depth-first search (DFS). The algorithm builds a path incrementally, one vertex at a time. Starting from any vertex, it attempts to extend the current path by adding an adjacent, unvisited vertex. If it reaches a dead end where no unvisited neighbor exists but not all vertices have been visited, it backtracks — removing the last vertex and trying a different neighbor. This pruning eliminates large portions of the search space without explicitly enumerating them. For example, if the current path is A -> B -> C and C has no unvisited neighbors, the algorithm will not explore any permutation starting with A -> B -> C, saving factorial work.

A more sophisticated approach uses dynamic programming with bitmasking, often called the Held-Karp algorithm. The key insight is to define a state DP[mask][v] which is true if there exists a path that visits exactly the set of vertices represented by the bitmask 'mask' and ends at vertex v. The transition is: DP[mask | (1 << u)][u] = true if DP[mask][v] is true and there is an edge from v to u. The base cases are DP[1 << v][v] = true for all v. The answer is true if any DP[(1 << n) - 1][v] is true. This method trades space for time, reducing the time complexity from O(n!) to O(n² * 2ⁿ), which is still exponential but dramatically faster for n up to 20-25 and is the basis for many exact solvers.

Complexity Class and Reductions

The hamiltonian path problem is NP-complete, which can be shown by a polynomial-time reduction from the Hamiltonian cycle problem or from 3-SAT. The standard reduction from Hamiltonian cycle to Hamiltonian path is elegant: given a graph G for which we want to test for a Hamiltonian cycle, we pick an arbitrary vertex v, split it into two vertices v_in and v_out, connect v_in to all incoming neighbors of v and v_out to all outgoing neighbors (or all neighbors in undirected case), and ask if there is a Hamiltonian path from v_in to v_out in the new graph G'. This reduction proves that Hamiltonian path is at least as hard as Hamiltonian cycle.

Conversely, the problem is in NP because a proposed solution — a permutation of vertices — can be verified in linear time O(n + m) by checking that it contains each vertex exactly once and that every consecutive pair is an edge. This easy verification versus hard discovery is the hallmark of NP-complete problems.

Implementation

Implementing a solver for the hamiltonian path problem requires careful handling of graph representation, visited state, and recursion. Below are four distinct Python implementations, from simple backtracking to optimized dynamic programming, each illustrating a different algorithmic strategy and trade-off.

1. Classic Backtracking with DFS

This implementation is the most accessible and works well for sparse graphs and small n. It tries every starting vertex and recursively explores paths, backtracking when stuck.

def has_hamiltonian_path_backtracking(graph):
    """
    graph: adjacency list dict {vertex: [neighbors]}
    Returns: (bool, path) tuple
    """
    n = len(graph)
    vertices = list(graph.keys())
    # Map vertex to index for visited set
    vertex_to_idx = {v: i for i, v in enumerate(vertices)}

    def dfs(path, visited):
        # If path covers all vertices, success
        if len(path) == n:
            return True, path.copy()
        
        last = path[-1]
        for neighbor in graph[last]:
            idx = vertex_to_idx[neighbor]
            # Check if neighbor not visited
            if not (visited >> idx) & 1:
                visited |= (1 << idx)
                path.append(neighbor)
                found, result = dfs(path, visited)
                if found:
                    return True, result
                # Backtrack
                path.pop()
                visited ^= (1 << idx)
        return False, []

    # Try each vertex as starting point
    for start in vertices:
        idx = vertex_to_idx[start]
        visited = 1 << idx
        found, result = dfs([start], visited)
        if found:
            return True, result
    return False, []

# Example usage:
# graph = {'A': ['B', 'C'], 'B': ['A', 'C', 'D'], 'C': ['A', 'B', 'D'], 'D': ['B', 'C']}
# print(has_hamiltonian_path_backtracking(graph))

2. Dynamic Programming with Bitmask (Held-Karp)

This DP approach is significantly faster for dense graphs and guarantees O(n² * 2ⁿ) time. It is the standard exact algorithm for n <= 22.

def has_hamiltonian_path_dp(graph):
    """
    DP with bitmasking. graph as adjacency matrix or adjacency set.
    Returns True if Hamiltonian path exists.
    """
    vertices = list(graph.keys())
    n = len(vertices)
    idx_map = {v: i for i, v in enumerate(vertices)}
    
    # Convert to adjacency set of indices for O(1) lookup
    adj = [set() for _ in range(n)]
    for v, neighbors in graph.items():
        vi = idx_map[v]
        for nb in neighbors:
            adj[vi].add(idx_map[nb])

    # dp[mask][v] = True if path exists covering mask ending at v
    dp = [[False] * n for _ in range(1 << n)]
    parent = [[-1] * n for _ in range(1 << n)]

    # Initialize: path of length 1 ending at each vertex
    for i in range(n):
        dp[1 << i][i] = True

    for mask in range(1 << n):
        for last in range(n):
            if not dp[mask][last]:
                continue
            # Try to extend to neighbor 'nxt' not in mask
            for nxt in range(n):
                if (mask >> nxt) & 1 == 0 and nxt in adj[last]:
                    new_mask = mask | (1 << nxt)
                    if not dp[new_mask][nxt]:
                        dp[new_mask][nxt] = True
                        parent[new_mask][nxt] = last

    full_mask = (1 << n) - 1
    for v in range(n):
        if dp[full_mask][v]:
            # Reconstruct path (optional)
            path = []
            mask = full_mask
            curr = v
            while curr != -1:
                path.append(vertices[curr])
                prev = parent[mask][curr]
                mask ^= (1 << curr)
                curr = prev
            path.reverse()
            return True, path
    return False, []

3. Optimized Backtracking with Pruning

For larger sparse graphs, simple pruning heuristics can cut the search dramatically. This version checks for disconnected unvisited components and degree-1 vertices.

def has_hamiltonian_path_pruned(graph):
    """
    Backtracking with connectivity pruning.
    """
    vertices = list(graph.keys())
    n = len(vertices)
    idx_map = {v: i for i, v in enumerate(vertices)}
    adj_list = {idx_map[v]: [idx_map[x] for x in graph[v]] for v in vertices}

    def is_connected_unvisited(visited_mask):
        # Check if unvisited vertices form a connected subgraph
        # Find first unvisited vertex
        start = -1
        for i in range(n):
            if ((visited_mask >> i) & 1) == 0:
                start = i
                break
        if start == -1:
            return True
        # BFS only through unvisited vertices
        stack = [start]
        seen = {start}
        while stack:
            u = stack.pop()
            for w in adj_list[u]:
                if ((visited_mask >> w) & 1) == 0 and w not in seen:
                    seen.add(w)
                    stack.append(w)
        # Count unvisited
        unvisited_count = 0
        for i in range(n):
            if ((visited_mask >> i) & 1) == 0:
                unvisited_count += 1
        return len(seen) == unvisited_count

    def dfs(path, visited_mask):
        if len(path) == n:
            return True
        # Pruning: if remaining graph is disconnected, fail early
        if not is_connected_unvisited(visited_mask):
            return False
        last = path[-1]
        for nxt in adj_list[last]:
            if ((visited_mask >> nxt) & 1) == 0:
                path.append(nxt)
                if dfs(path, visited_mask | (1 << nxt)):
                    return True
                path.pop()
        return False

    for s in range(n):
        if dfs([s], 1 << s):
            return True
    return False

4. Hamiltonian Path in a DAG (Polynomial Time)

If the graph is a Directed Acyclic Graph (DAG), the hamiltonian path problem becomes solvable in linear time via topological sorting. A DAG has a Hamiltonian path if and only if its topological order forms a Hamiltonian path.

from collections import deque

def hamiltonian_path_dag(graph):
    """
    Finds Hamiltonian path in DAG in O(V+E).
    graph: adjacency list for DAG {u: [v]}
    Returns path list or None.
    """
    vertices = list(graph.keys())
    # Ensure all vertices appear as keys
    for v in list(graph.values()):
        for nb in v:
            if nb not in graph:
                graph[nb] = []

    vertices = list(graph.keys())
    n = len(vertices)
    indegree = {v: 0 for v in vertices}
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1

    # Kahn's algorithm for topological sort
    queue = deque([v for v in vertices if indegree[v] == 0])
    topo = []
    while queue:
        u = queue.popleft()
        topo.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    if len(topo) != n:
        return None  # Not a DAG

    # Check if consecutive vertices in topo order are connected
    for i in range(n - 1):
        if topo[i+1] not in graph[topo[i]]:
            return None  # No Hamiltonian path
    return topo

# DAG example: {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []} -> No Hamiltonian path
# DAG example: {'A': ['B'], 'B': ['C'], 'C': ['D'], 'D': []} -> Path A->B->C->D

Step-by-Step Example

Let us walk through a concrete example to make the backtracking and DP logic tangible. Consider an undirected graph with 4 vertices: A, B, C, D and edges: A-B, A-C, B-C, B-D, C-D. Visually, this is a diamond shape with a diagonal B-C. We want to determine if a Hamiltonian path exists.

Step 1: Attempt starting at A. The algorithm initializes path = [A], visited = {A}. From A, neighbors are B and C. It first tries B. Path becomes [A, B].

Step 2: From B, extend. Unvisited neighbors of B are C and D (A is visited). The DFS picks C first (order depends on adjacency list). Path = [A, B, C]. Unvisited neighbor of C is D (since A, B visited). Path = [A, B, C, D]. All 4 vertices are visited, and each consecutive pair is an edge (A-B yes, B-C yes, C-D yes). Success! The algorithm returns path A -> B -> C -> D.

Had the algorithm chosen differently, it might have explored [A, B, D] next. From D, the only neighbors are B and C, both visited except C is unvisited but D is not connected to A, so from [A, B, D], the only unvisited neighbor is C, and D-C is an edge, so [A, B, D, C] is also a valid Hamiltonian path. In fact, this graph has multiple Hamiltonian paths.

Step 3: How DP would solve it. The DP table builds up from smaller masks. Base: dp[{A}][A]=True, dp[{B}][B]=True, etc. For mask {A,B}, dp[{A,B}][B]=True because dp[{A}][A] and edge A-B exists. Similarly dp[{A,B}][A]=True via B-A. Iteratively, for mask {A,B,C}, dp[{A,B,C}][C]=True because dp[{A,B}][B] and edge B-C exists. Finally, for full mask {A,B,C,D}, dp[full][D]=True because dp[{A,B,C}][C] and edge C-D exists. The parent pointers allow reconstruction of the same path.

Step 4: A failure case. If we remove edge C-D, the graph becomes A-B, A-C, B-C, B-D. Starting at A -> B -> C, C has no unvisited neighbors (D is not adjacent to C), so it backtracks to A -> B -> D, but D has no unvisited neighbors and path length is 3 < 4, so it backtracks further. Starting at D -> B -> A -> C succeeds (D-B, B-A, A-C), so even this modified graph still has a Hamiltonian path. To make it fail, remove both B-D and C-D, isolating D — then no Hamiltonian path exists.

Tracing the Search Tree

The search tree for this graph starting at A has branching factor 2 at the first level (B,C), then branching factor up to 2 at the next level. Without pruning, the worst-case explores all permutations starting with A (6 permutations). With connectivity pruning, branches that disconnect the remaining graph are cut early. Visualizing this tree helps understand why ordering heuristics — trying vertices with fewer onward connections first (Warnsdorff-like rule) — can dramatically reduce runtime in practice.

Complexity Analysis

Analyzing the complexity of the hamiltonian path problem requires distinguishing between the inherent complexity of the problem itself and the complexity of specific algorithms used to solve it. The problem is NP-complete, so no polynomial-time algorithm is known for general graphs, and it is widely believed none exists.

Brute-force permutation checking generates all n! permutations and checks each in O(n) time, yielding O(n * n!) time and O(n) space. Backtracking improves average performance but retains O(n!) worst-case time because in the worst case (e.g., a complete graph or a graph with no Hamiltonian path) it still explores nearly all permutations. Its space is O(n) for recursion stack plus O(n²) for adjacency matrix.

The Held-Karp DP algorithm is the best known exact algorithm for general graphs. It runs in O(n² * 2ⁿ) time and O(n * 2ⁿ) space. While still exponential, 2ⁿ grows far slower than n! — for n=20, n! is about 2.4e18 while n² * 2ⁿ is about 4e8, making DP feasible where brute force is not. For sparse graphs, backtracking with pruning often outperforms DP in practice, but DP provides a predictable worst-case bound.

Special graph classes admit polynomial-time solutions. As shown in the DAG code, a Hamiltonian path in a DAG can be found in O(V + E) time. Similarly, graphs with bounded treewidth, cactus graphs, and graphs where every vertex has degree at least n/2 (Dirac's theorem guarantees a Hamiltonian cycle) have efficient algorithms. This highlights that hardness comes from general graph structure, not the path definition itself.

The best case for backtracking occurs when the graph is a simple line A-B-C-D and the algorithm guesses the correct start and order immediately, finding the path in linear time. The worst case occurs when no path exists, forcing exhaustive search. This variance means benchmarking must use both Hamiltonian and non-Hamiltonian instances to be meaningful.

Variations and Optimizations

The classic hamiltonian path problem has numerous variations that adapt it to different constraints and offer optimization opportunities. Understanding these variants is essential for applying the right model to a real problem.

Hamiltonian Cycle: Requires the path to return to the start vertex. Any Hamiltonian cycle contains a Hamiltonian path (by removing one edge), but not vice versa. To solve cycle via path, add a universal vertex connected to all others and look for a path, or simply check if a Hamiltonian path exists whose endpoints are adjacent.

Directed vs. Undirected: In directed graphs, edges have orientation, and the path must follow direction. This can make the problem harder in practice because branching is more constrained but pruning is less effective. The DP formulation handles both naturally by checking directed adjacency.

Fixed Endpoints (s-t Hamiltonian Path): Often we need a path that starts at s and ends at t. This is also NP-complete and can be reduced to the general problem by adding two new vertices s' and t' connected only to s and t respectively. This variant is common in routing where start and depot are predetermined.

Optimization Variants: The Shortest Hamiltonian Path (or Path TSP) seeks the minimum-weight Hamiltonian path in a weighted graph. The Longest Hamiltonian Path finds the maximum-weight path. Both are NP-hard and generalize the decision problem.

Key Optimizations

Beyond the core DP, several heuristics dramatically improve practical performance. Degree-based pruning: if the remaining unvisited subgraph has more than two vertices of degree 1, no Hamiltonian path can exist (a path has at most two endpoints). Connectivity pruning, as implemented above, ensures the unvisited vertices remain connected; otherwise backtrack immediately. Memoization with bitmask (DP + DFS) caches failed states: if we have visited mask ending at v and it was proven to lead to no solution, never revisit it. This hybrid is often called DP with DFS and achieves Held-Karp bounds with less memory in sparse cases.

For large graphs where exact solutions are infeasible, heuristics like nearest-neighbor greedy, 2-opt local search, and genetic algorithms can find near-Hamiltonian paths quickly. While they do not guarantee visiting all vertices exactly once, they are invaluable for TSP-like applications where covering most vertices with a short path is acceptable. Another powerful technique is reduction to SAT or ILP and using modern solvers (e.g., Glucose, Gurobi), which often solve instances with hundreds of vertices that naive backtracking cannot.

Real-World Applications

Despite its theoretical hardness, the hamiltonian path problem appears surprisingly often in practical engineering and scientific domains. Its ability to model exact-once visitation makes it a natural fit for sequencing and routing tasks.

In genomics and bioinformatics, DNA fragment assembly can be modeled as a Hamiltonian path problem. Each fragment is a vertex, and an edge exists if two fragments overlap significantly. A Hamiltonian path corresponds to an ordering of fragments that reconstructs the original genome. While modern assemblers often use Eulerian paths in de Bruijn graphs for efficiency, the overlap-layout-consensus paradigm is fundamentally Hamiltonian and is still used for long-read sequencing.

In manufacturing and robotics, a drill or laser must visit a set of holes or points on a circuit board exactly once while minimizing travel time. This is the Path TSP, whose feasibility version is Hamiltonian path. Similarly, a robotic arm picking items from a warehouse or a 3D printer laying material benefits from Hamiltonian path planning to avoid redundant movements.

In networking and distributed systems, Hamiltonian paths are used for token-based mutual exclusion, linear arrangement of virtual machines to minimize communication overhead, and testing network topology. A Hamiltonian path that visits each router once can be used to disseminate a message with minimal duplication. In peer-to-peer networks, constructing an overlay with a Hamiltonian path ensures each node can be visited in a single sweep for maintenance or updates.

In databases and web crawling, query optimization for join ordering can be seen as finding an optimal Hamiltonian path through tables where edge weights represent join costs. Web crawlers that wish to visit each page in a domain exactly once without revisiting (to respect politeness and avoid loops) face a Hamiltonian path challenge, though they typically use BFS/DFS approximations due to scale.

Even in operating systems and compilers, instruction scheduling and register allocation can be reduced to Hamiltonian path variants when ordering operations with dependencies. The key takeaway is that whenever the cost of revisiting a node is high — whether due to time, money, or resource constraints — the Hamiltonian path model becomes relevant, and its NP-completeness informs whether to pursue exact, approximate, or heuristic methods.

Comparison with Alternatives

Choosing the right path problem is critical. Using a Hamiltonian path solver when an Eulerian path would suffice wastes exponential time, while using an Eulerian approach for a Hamiltonian requirement yields incorrect results. The table below provides a detailed feature comparison to guide selection.

The most important distinction for practitioners is between Hamiltonian and Eulerian. If your problem requires covering edges (e.g., inspecting every road, checking every bridge, delivering mail along streets), the Eulerian path is both correct and efficiently solvable. If it requires covering vertices (e.g., visiting every city, sequencing every fragment), you need Hamiltonian and must confront exponential complexity. TSP is essentially the optimization version of Hamiltonian cycle on a complete weighted graph, so any TSP solver can solve Hamiltonian cycle by setting weight 0 for existing edges and 1 for non-edges and asking if optimal tour weight is 0.

Another alternative is the Longest Path problem, which seeks the longest simple path (no repeated vertices) without requiring it to cover all vertices. In general graphs, longest path is also NP-hard and even harder to approximate, but in DAGs it is solvable in linear time via DP, just like Hamiltonian path in DAGs. This shared tractability on DAGs underscores how acyclicity tames many hard path problems.

Common Mistakes and Best Practices

Implementing and reasoning about the hamiltonian path problem is error-prone. Even experienced developers make subtle mistakes that lead to incorrect results or exponential blowup on trivial instances.

Mistake 1: Confusing Path with Cycle. Many implementations check for a Hamiltonian path but inadvertently require the endpoints to be connected, thus solving the cycle variant. Always clarify whether the path needs to be open or closed. If you reduce cycle to path, remember to handle the endpoint adjacency check separately.

Mistake 2: Not Trying All Start Vertices. A common bug in backtracking is to start DFS only from vertex 0. A graph may have a Hamiltonian path starting at vertex 3 but not at 0. The outer loop over all start vertices is essential unless the problem specifies fixed endpoints. Similarly, for directed graphs, indegree/outdegree can prune start candidates but not eliminate the loop entirely.

Mistake 3: Inefficient Visited Representation. Using a Python set or list for visited and checking membership with 'in' inside tight recursion leads to O(n) overhead per step. Using a bitmask integer or boolean array with O(1) checks is critical for performance. For n > 64, consider Python's integers (arbitrary precision) or a frozenset cache.

Mistake 4: Forgetting to Escape < > in HTML or Mis-handling Recursion Limits. When rendering code in web contexts, unescaped < and > break HTML. In Python, deep recursion for n > 1000 will hit recursion limits; use iterative stack or increase recursion limit. Also, failing to copy the path when returning results leads to mutation bugs where the returned path changes during backtracking.

Best Practices

• Choose representation wisely: Use adjacency sets for O(1) edge existence checks in DP, and adjacency lists for sparse graph DFS. For dense graphs, adjacency matrices may be faster due to cache locality.
• Apply ordering heuristics: Sort neighbors by degree ascending (fewest options first) to fail faster — this is the Minimum Remaining Values heuristic from constraint satisfaction.
• Use memoization: Cache (mask, last) states that are proven dead ends to avoid re-exploring the same subproblem from different paths. This converts naive DFS into DP.
• Detect special cases early: Check if graph is DAG, complete, or has articulation points. If the graph is disconnected, immediately return false. If n <= 1, handle trivially.
• Test on both positive and negative instances: Many solvers pass on graphs with a Hamiltonian path but time out or incorrectly return true on graphs without one. Include the Petersen graph (no Hamiltonian cycle but has Hamiltonian path) and other known hard examples in your test suite.
• Consider using existing solvers: For production use with n > 30, do not write your own solver. Reduce to SAT and use PySAT or use OR-Tools, which implement highly optimized branch-and-bound and pruning.

Interview Questions

Because the hamiltonian path problem is a classic NP-complete problem, it appears frequently in algorithm interviews to test understanding of complexity, backtracking, and dynamic programming. Here are common questions and how to approach them.

Q1: How do you check if a Hamiltonian path exists in a DAG? What is the complexity?

Answer: A DAG has a Hamiltonian path if and only if its topological sort is unique and consecutive vertices in the topological order are connected by edges. Algorithm: compute topological order via Kahn's algorithm or DFS in O(V+E). Then iterate through the order and verify that for every i, there is an edge from topo[i] to topo[i+1]. If any consecutive pair is missing, no Hamiltonian path exists. This is O(V+E) time and O(V) space, far better than the exponential general case. Be prepared to prove both directions: if such a path exists, it must be the topological order; if the topological order has all consecutive edges, it is the Hamiltonian path.

Q2: Reduce Hamiltonian Cycle to Hamiltonian Path (or vice versa) and explain why this proves NP-completeness.

Answer: To reduce Hamiltonian Cycle to Hamiltonian Path: given graph G, pick a vertex v, split it into v_in and v_out, connect v_in to all neighbors of v that were incoming (or all neighbors in undirected case) and v_out to all neighbors, and add no edge between v_in and v_out. Then G has a Hamiltonian cycle iff the new graph G' has a Hamiltonian path from v_in to v_out. Since Hamiltonian Cycle is known NP-complete, and the reduction is polynomial, Hamiltonian Path is NP-hard. Since it is also in NP (certificate is the path itself), it is NP-complete. Interviewers want to see you can construct the reduction and argue both correctness and polynomial time.

Q3: Implement a function to find a Hamiltonian path using DP with bitmasking. What are the time and space complexities?

Answer: This tests ability to write Held-Karp DP as shown in the Implementation section. Key points to mention: dp[mask][v] boolean, initialization dp[1<<v][v]=True, transition dp[mask|1<<u][u] |= dp[mask][v] if edge v->u, answer is any dp[full][v]. Complexity is O(n² * 2ⁿ) time and O(n * 2ⁿ) space. Optimize space by using only two layers if you only need existence, but need full table for reconstruction. Mention that this works for n up to ~22 in Python, ~25 in C++ with bitset optimizations.

Q4: What is the difference between Hamiltonian Path and Eulerian Path? Give an example graph that has one but not the other.

Answer: Hamiltonian visits each vertex once, Eulerian visits each edge once. Eulerian has a simple characterization (connected and 0 or 2 vertices of odd degree for undirected), Hamiltonian has none. Example: Consider a graph that is a star with center C connected to leaves A,B,D. It has an Eulerian trail? No, it has 4 vertices of odd degree (center degree 3 odd, leaves degree 1 odd) so no Eulerian path. It has no Hamiltonian path that covers all 4 vertices without repeating? Actually A-C-B is a path covering 3, but to cover all 4 you need to revisit C, so no Hamiltonian path either. Better example: A square cycle A-B-C-D-A has both. A graph shaped as a "theta": two vertices connected by three disjoint paths has an Eulerian trail but no Hamiltonian path covering all intermediate vertices without reuse. Conversely, the complete graph K4 has Hamiltonian paths but also Eulerian circuits (since all degrees odd? K4 degrees 3 odd, so no Eulerian circuit but has Eulerian trail). Provide clear small graphs and degree analysis.

Q5: How would you handle a graph with 1000 vertices where you need to find a Hamiltonian path? Exact vs. heuristic?

Answer: Exact algorithms are infeasible for n=1000 (2ⁿ is astronomical). You must discuss heuristics and approximations: use greedy construction, local search (2-opt, 3-opt), simulated annealing, genetic algorithms, or reduce to TSP and use Concorde/LKH solvers which handle up to 10k vertices heuristically. Also discuss special structure: if graph is dense (Dirac's condition degree >= n/2 guarantees Hamiltonian cycle), you can use constructive proofs. If sparse, use articulation point and connectivity pruning to quickly prove impossibility. The key insight interviewers seek is recognizing NP-completeness implies you should not attempt exact exponential solution at scale, but pivot to heuristics, constraints, or special-case polynomial algorithms.