7
$\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?

Improve this question
$\endgroup$
5
  • 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$ Commented 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$ Commented 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$ Commented Nov 12, 2016 at 15:26
  • $\begingroup$ You may want to check out our reference questions. $\endgroup$ Commented Nov 12, 2016 at 18:41
  • $\begingroup$ In case someone else was wondering why this doesn't prove NP-completeness: cstheory.stackexchange.com/q/138/50429 $\endgroup$ Commented Feb 6, 2023 at 10:29

3 Answers 3

Reset to default
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.

Improve this answer
$\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$ Commented 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$ Commented 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$ Commented Apr 4, 2021 at 20:48
  • $\begingroup$ @Ari This answer is about simple paths, yes. $\endgroup$ Commented 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 directed path of weight $-(n-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\}$.

Improve this answer
$\endgroup$
0
$\begingroup$

Given an HP (Hamiltonian path) instance ($G=(V,E),s,t$), we define a Shortest-Simple-Path instance ($G,s,t,w,L$) as follows.

We simply let the weight $w(e)$ of every edge $e∈E$ be $−1$ and let $L=−(n−1)$. ($n=|V|$ is the number of vertices in $G$.) So, in this instance, we need to know whether there is a simple path in $G$ from $s$ to $t$ of weight at most $−(n−1)$ or not.

As all weights are $−1$, this is the same as whether there is a simple path in $G$ from $s$ to $t$ with at least $n−1$ edges or not. Such a path must be a Hamiltonian path in $G$ from $s$ to $t$ as $G$ contains only $n$ vertices. Thus, $G$ contains a Hamiltonian path from $s$ to $t$ if and only if the shortest simple path from $s$ to $t$ in $G$ has cost at most $−(n−1)$. This proves HP $≤_P$ Shortest-Simple-Path.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.