# Proving that the shortest path problem between two vertices $s$ and $t$ in a graph is NP-complete

How to show that the Shortest path problem between two vertices $s$ and $t$ (finding a minimum weighted path between $s$ and $t$) in a graph is NP-complete? I received the following prof in combinatorial optimization lecture which I didn't understood (I stressed the moment that I didn't understood).

Let be :

• $(P_1)$ the Hamiltonian path problem

The Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both problems are NP-complete. From wikipedia.

Does it exists an Hamiltonian path in G?

• and $(P_2)$ the Shortest path problem in an oriented graph.

If G is the graph within which we search such an Hamiltonian path we transform $G$ into $\hat G$ replacing each edges $(i,j)$ with two edges $(i,j)$ and $(j,i)$.

FOR EACH (edges {i,j} in G)
we erase (i,j) and (j,i)
and give a weight of $-1$ and we calculate the shortest path from i→j.

IF the path length is -(n-1)
THEN this is an hamiltonian path in G

FOR END

IF FOR ALL(edges the length between paths is greater than -(n-1))
THEN It means that an Hamiltonian path doesn't exists.

• Why does "if the path length is -(n-1) then this is an hamiltonian path in G" in the algorithm?
• And why if for all edges the length between paths is greater than -(n-1) it means that an Hamiltonian path doesn't exists?

Maybe if you were kind to help me understand with a visual example I would better understand?

• And last but not least, how did we proves it was NP complete?
• This actually doesn't prove that the problem is NP-complete, since it's an oracle reduction rather than a many-one reduction. Maybe your professor or TA should brush up on the basics. – Yuval Filmus Nov 12 '16 at 15:08
• @YuvalFilmus What are oracle reduction and many-one reduction? I only heard about reduction as : Let be $(P_1)$ and $(P_2)$, two reconnaissance problem, we say that $(P_1)$ is reducted (or reducible) to $(P_2)$ if * It exists an algorithm for $(P_1)$ that calls to an algorithm of $(P_2)$. * $(P_1)$ is polynomial. I don't fully understand this definition, especially the last condition. – Revolucion for Monica Nov 12 '16 at 15:14
• This defined an oracle reduction. NP-completeness is defined with a different notion of reduction, many-one reduction. There are many online resources about both types of reductions. Sometimes oracle reductions are called Cook reductions or Turing reductions, and many-one reductions are sometimes called Karp reductions. This should give you enough keywords to search for. – Yuval Filmus Nov 12 '16 at 15:26
• You may want to check out our reference questions. – Raphael Nov 12 '16 at 18:41

For the shortest path problem (SPP) to be NP-complete, it is crucial you allow negative edge weights. Then, there is a simple polynomial-time reduction from the Hamiltonian path problem to SPP. In other words, you take an arbitrary instance $I$ of the Hamiltonian path problem, and construct an instance $I'$ of SPP such that $I$ has a solution if and only if $I'$ has a solution. To make the reduction work, you only need to set up the edge weights in $I'$ suitably.
• Thank you for your answer! Yet, by saying : construct an instance $I'$ of SPP such that $I$ has a solution if and only if $I'$ has a solution. So giving a weight of -1 and calculate the shortest path from i→j. and testing IF the path length is -(n-1) gives such an $I'$, isn't it? The thing I don't understand is why the condition test if it has a solution, does it mean that we got through another vertices before concluding? Last, I don't understand your last sentence. – Revolucion for Monica Nov 12 '16 at 23:12
• @Marine1 Yes, so in other words, the instance of $I'$ will consists of exactly same graph it is in $I$, and you set the weight of every edge to -1. Now there are two directions to prove: (1) if $I$ has a solution, then $I'$ has a solution, and (2) if $I'$ has a solution, then $I$ has a solution. If I were you, I would insist on having a reduction that uses the definition that has been given to you (many-one reduction, like you describe in your comment to your question). Basically, you don't need to know about oracle reductions at this point. – Juho Nov 13 '16 at 9:09