4
$\begingroup$

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?
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 12 '16 at 15:08
  • $\begingroup$ @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. $\endgroup$ – ThePassenger Nov 12 '16 at 15:14
  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 12 '16 at 15:26
  • $\begingroup$ You may want to check out our reference questions. $\endgroup$ – Raphael Nov 12 '16 at 18:41
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ThePassenger Nov 12 '16 at 23:12
  • $\begingroup$ @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. $\endgroup$ – Juho Nov 13 '16 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.