Hamiltonian path problem

The decision problem of determining whether a graph contains a path that visits every vertex exactly once.

Graph theory: The mathematical study of graphs, structures made of vertices connected by edges. Hamiltonian paths are defined by the vertices and edges of a graph.
Backtracking: A search method that builds candidate solutions incrementally and abandons partial candidates that cannot succeed. It explores vertex sequences and prunes those that cannot extend to a spanning path.
Eulerian path: A trail in a graph that traverses every edge exactly once. It covers edges rather than requiring each vertex to appear exactly once.
Knight's tour: A sequence of moves by a chess knight that visits every square of a board exactly once. It is a Hamiltonian path problem on the graph of legal knight moves.
Path (graph theory): A sequence of distinct vertices in a graph, with consecutive vertices joined by edges. A Hamiltonian path is a path whose sequence includes every vertex.
Subset dynamic programming: A dynamic programming technique whose states represent subsets of elements and associated partial solutions. States can record which vertices have been visited and which vertex ends the path.
Traveling salesperson problem: The optimization problem of finding a minimum-cost tour that visits every city and returns to the start. It adds edge costs and a return requirement to a Hamiltonian-cycle-style search.
Genome assembly: The reconstruction of a genome sequence from shorter DNA fragments or sequencing reads. Some assembly formulations seek a path through a graph of overlapping fragments.
Hamiltonian cycle: A cycle in a graph that visits every vertex exactly once before returning to its start. It adds a closing edge to the kind of spanning path tested here.
Held–Karp algorithm: A dynamic programming algorithm for the traveling salesman problem with exponential time and space requirements. Its subset recurrence also solves Hamiltonian path by tracking visited vertices and endpoints.

Linked from 3 pages

Hamiltonian pathBroader topic: It formalizes the existence question for this graph structure.