HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Negative simple path NP-Complete

Submitted by: @import:stackexchange-cs··
0
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

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.

Context

StackExchange Computer Science Q#104684, answer score: 2

Revisions (0)

No revisions yet.