# Is “Find the shortest tour from a to z passing each node once in a directed graph” NP-complete?

Given a directed graph with the following attributes: - a chain from node $a$ to node $z$ passing nodes $b$ to $y$ exists and is unidirectional. - additionally a set of nodes having bidirectional vertices to at least two of the nodes $a \ldots z$ exists. These nodes are connected in a second unidirectional chain.

(the red route is the requested result, the squares are the first chain (unidirectional) and the circles are the second chain (unidirectional). $1$ is the start node and $5$ is the destination node.)

Is it possible to find the shortest path from $a$ to $z$ that includes nodes $b$ to $y$ and the additional nodes once without probing all possibilities?

I think the problem is roughly the same as the minimal traveling salesman problem since adding a vertex from $z$ to $a$ will result in the min-TSP - but this problem is slightly easier since a path from $a$ to $z$ is already known.

• Would you be able to add a sketch of an example graph? (Just to help with understanding the setup) – Luke Mathieson May 16 '13 at 1:55

Suppose that the nodes on the bottom line are $B_1,B_2,...,B_n$ and the nodes on the upper line are $U_1,U_2,U_m$. You need to find an Hamiltonian path from $B_1 \to B_n$.
If you are on node $B_i$, move to the first node $U_j$ linked to it (first means leftmost in the upper chain), then scan $U_{j+1}, U_{j+2},...$ until you find a link from $U_{j+k}$ to $B_{i+1}$ and such that if $j+k<m$ there is another link from $B_{i+l}, l>i$ to $U_{j+k+1}$ (that will allow you to complete the upper line). If such $U_{j+k}$ exists, add edges $B_{i}\to U_{j} \to ... \to U_{j+k} \to B_{i+1}$ to the final path, delete those nodes from the set and repeat the procedure from $B_{i+1}$. If such $U_{j}$ doesn't exist, add the edge $B_{i} \to B_{i+1}$ and repeat the procedure from $B_{i+1}$.
• @urzeit: ??? If you have a path that visits all nodes, then it cannot be shorter than an Hamiltonian path on those nodes (if there are $n$ nodes then an Hamiltonian path has $n-1$ edges) – Vor Oct 1 '13 at 12:04