The Directed Hamiltonian Path Problem
problem involves an oriented graph. This means a collection
of points (vertices) and of arrows (oriented paths) from one point
to another. A nice way to think about the problem (following
Fred Hapgood) is to turn the graph into the route map for an airline:
each vertex represents an airport
and each arrow
represents a flight from one airport to another.
We designate a Start airport (say, Fresno) and a
Finish (say, Boston).
In these terms, the directed Hamiltonian path problem for this
graph is to
find a sequence of flights beginning in Fresno, ending in Boston
and visiting each airport in the route map exactly once.
In usual graph terminology, such a sequence is called a
This problem is simple to state and, when there are only
few airports and flights, can be solved by inspection.
But the amount
of computation necessary to settle the question, using the most
efficient algorithms known at present, grows exponentially with
the size of the route map: essentially the only way is to go down
the list of all possible chains of flights until a solution is found or
until the list is exhausted.
On the other hand given any list of airports, even in a very
large graph, checking if that list
defines a Hamiltonian path or not
just means checking for each airport if one of its flights
leads to the next airport on the list. The number of
is bounded by some
constant times the number of airports times the maximum number of
flights leaving an airport.
The combination of exponential
growth of the list to be searched, and polynomial growth of
the length of the checking algorithm, makes this an