The ABC of DNA Computing


2. The Directed Hamiltonian Path Problem

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:

Hamiltonian Airways Route Map
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 Hamiltonian path. The combination of exponential growth of the list to be searched, and polynomial growth of the length of the checking algorithm, makes this an NP problem.

© copyright 2000, American Mathematical Society.