# 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

If I understood well the question, things are clearer if you draw the graph in this way:

And you can use the following polynomial time greedy algorithm to find an Hamiltonian path from the two endpoint nodes of the bottom line.

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}$.

• You are right. This graph makes the situation clearer. Perhaps I would have found the answer if i had drawn it that way ;-) – urzeit May 16 '13 at 8:09
• Sorry, I had to remove the solution mark: I asked for the shortest hamilton-path in the graph. Your algorighm yields a hamilton-path, right? – urzeit Oct 1 '13 at 10:07
• @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
• I didn't write, that the graph is weighted. By "shortest" path, I meant a path with minimal weight-sum. Re-accepted your answer, since I didn't write that. – urzeit Oct 1 '13 at 12:10