patternMinor
Proving that the shortest simple path problem between two vertices $s$ and $t$ in a graph is NP-complete
Viewed 0 times
provingpaththesimpleproblemshortestgraphtwobetweenthat
Problem
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.
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#65925, answer score: 2
Revisions (0)
No revisions yet.