patternMinor
Negative simple path NP-Complete
Viewed 0 times
pathsimplenegativecomplete
Problem
Given a graph $G=(V,E)$, and positive and negative edge weights, negative path problem asks if there is a simple path with negative total weight from $s$ to $t$ where $s,t \in V$
My approach was to reduce this from the Hamiltonian path and I know I should somehow force the solver to go through as many vertices as it can to get a Hamiltonian path but I am not sure how to construct such a reduction
My approach was to reduce this from the Hamiltonian path and I know I should somehow force the solver to go through as many vertices as it can to get a Hamiltonian path but I am not sure how to construct such a reduction
Solution
You can reduce from the Hamiltonian path problem. Given an instance of the Hamiltonian path problem with $n$ vertices:
-
Add a start vertex $s$ and an ending vertex $t$.
-
For every vertex $v$ that is not $s$ or $t$, add edges $(s, v)$ and $(v, t)$ with weight $n-1$ and $n-2$ respectively.
-
For every other edge, assign it weight $-2$.
Now the previous graph has an Hamiltonian path if and only if there is a simple path with negative total weight from $s$ to $t$ in the new graph.
-
Add a start vertex $s$ and an ending vertex $t$.
-
For every vertex $v$ that is not $s$ or $t$, add edges $(s, v)$ and $(v, t)$ with weight $n-1$ and $n-2$ respectively.
-
For every other edge, assign it weight $-2$.
Now the previous graph has an Hamiltonian path if and only if there is a simple path with negative total weight from $s$ to $t$ in the new graph.
Context
StackExchange Computer Science Q#104684, answer score: 2
Revisions (0)
No revisions yet.