Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
Problem Detail: 

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?
Asked By : Marine1

Answered By : Juho

In fact, it does not prove NP-completeness (see a list of our related reference questions).

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback