2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why do you think this problem is NP-complete? Do you mean to require it to be a simple path? Or can the path repeat edges? If you mean it to be a simple path, please state that requirement in the body of the question. I suggest checking the original source to see what it says. Can you edit the question to cite the original source for this problem, and to state the problem more carefully? $\endgroup$ – D.W. Feb 21 at 22:20
  • $\begingroup$ We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. We have some general resources on constructing reductions here: cs.stackexchange.com/q/11209/755, cs.stackexchange.com/q/1240/755 (I've previously shared these links with you). You might need to keep trying, as often it requires trial and error. $\endgroup$ – D.W. Feb 21 at 22:22
  • $\begingroup$ Hint: reduce from Hamiltonian $st$-path by constructing a new graph $G'$ with a new vertex $t'$ adjacent to $t$ added. You are free to place the weights on the edges: think about how you should do this so that $G$ has a Hamiltonian $st$-path if and only if $G'$ has a negative $st'$-path. $\endgroup$ – Juho Feb 22 at 8:29
  • $\begingroup$ Can the path contains repeated vertices (or equivalently, a cycle)? $\endgroup$ – xskxzr Feb 22 at 9:16
  • $\begingroup$ @xskxzr it is a simple path, I edited the question $\endgroup$ – Kaan Yolsever Feb 22 at 23:57
1
$\begingroup$

You can reduce from the Hamiltonian path problem. Given an instance of the Hamiltonian path problem with $n$ vertices:

  1. Add a start vertex $s$ and an ending vertex $t$.

  2. 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.

  3. 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.

$\endgroup$
1
$\begingroup$

Let $G=(V,E)$ be an instance of Hamiltonian $st$-path. Construct an instance of negative $st$-path $G'$ such that $G' = G$ with a new vertex $t'$ and the edge $tt'$ added. Set the weight of $tt'$ to $|V|-2$ and every other edge weight to $-1$.

The claim is that $G$ has a Hamiltonian $st$-path iff $G'$ has a negative $tt'$-path.

  • In the first direction, let $P$ be a Hamiltonian $st$-path in $G$. By definition, $P$ visits each vertex exactly once, so $P$ has total weight $1-|V|$ in $G$. So by taking $P \cup \{t,t'\}$ we have a path from $s$ to $t'$ in $G'$ with total weight $1-|V|+|V|-2 = -1$, as required.

  • In the second direction, suppose that there is a negative $st'$-path $P$ in $G'$. Because $t'$ has degree 1, any such $P$ must use the edge $tt'$ which has weight $|V|-2$. Further, as $P$ has negative total weight and the weight of every other edge is $-1$, it holds that $P$ also uses at least $|V|-1$ edges. In fact, as $P$ is simple, it uses exactly $|V|-1$ edges all of which are in $G$. So by taking $P \setminus \{t,t'\}$ we obtain a Hamiltonian $st$-path in $G$.

This completes the proof.

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