5
$\begingroup$

How to show that the shortest simple path problem between two vertices $s$ and $t$ (finding a minimum weight path between $s$ and $t$) in a graph is NP-complete? I saw the following proof in a combinatorial optimization lecture, which I didn't understood (I stressed the moment that I didn't understand).

Let $P_1$ be 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$?

Let $P_2$ be the shortest path problem in a directed graph.

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

For each edge $\{i,j\}$ in $G$, we erase $(i,j)$ and $(j,i)$ from $\hat{G}$, give a weight of $-1$ to all remaining edges, and calculate the shortest (simple) path from $i$ to $j$. If the path length is $-(n-1)$, then this is a Hamiltonian path in $G$. If we found no such path going over all edges, then $G$ has no Hamiltonian path.

  • Why is is the case that if the path has length $-(n-1)$ then it constitutes a Hamiltonian path in $G$?
  • Why if not such path has length $-(n-1)$ then $G$ has no Hamiltonian path?

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

Last but not least, how did we proves that Hamiltonian path is NP-complete?

$\endgroup$
4
  • 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$ Nov 12, 2016 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$ Nov 12, 2016 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$ Nov 12, 2016 at 15:26
  • $\begingroup$ You may want to check out our reference questions. $\endgroup$
    – Raphael
    Nov 12, 2016 at 18:41

2 Answers 2

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$
4
  • $\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$ Nov 12, 2016 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, 2016 at 9:09
  • $\begingroup$ Isn't this only true for shortest simple paths? Shortest path problem can be solved using classic algorithms if there are no negative cycles. $\endgroup$
    – Ari
    Apr 4, 2021 at 20:48
  • $\begingroup$ @Ari This answer is about simple paths, yes. $\endgroup$
    – Juho
    Apr 4, 2021 at 21:19
1
$\begingroup$

Suppose there is a simple path of weight $-(n-1)$ from $i$ to $j$. Since each edge has weight $-1$, this path must contain $n-1$ edges, and so it corresponds to a Hamiltonian path in the original graph.

Conversely, suppose that the original graph has a Hamiltonian path, say starting at $i$ and ending at $j$. This path leads to a path of weight $-1$ in $\hat{G}$ which doesn't use the edges $(i,j),(j,i)$, and so it will be found when considering the edge $\{i,j\}$.

$\endgroup$

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.