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

Problem Detail: 

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.

Asked By : urzeit

Answered By : Vor

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12036

3.2K people like this

 Download Related Notes/Documents