# Does a weighted graph have a path with weight zero?

Given a weighted digraph $G=(V,E)$, where each edge is associated with a weight (could be positive, negative, or zero). We define the weight of a path to be the sum of the weights along this path.

The question: given two vertices $s,t$, decide whether there is a (not necessarily simple) path from $s$ to $t$ such that the weight of the path is 0.

It is not very difficult to see that this problem is in NP. I am wondering whether there is a polynomial time algorithm, or it is NP-hard.

• Why do you think the problem is in NP? After all, the solution path (the certificate) can have potentially unbounded length. Jul 10, 2017 at 20:00
• Why do you think the problem is in NP? After all, the solution path (the certificate) can have potentially unbounded length. Jul 10, 2017 at 20:01
• Showing NP-hardness of this and relate problem is an exercise I often give when teaching reductions. Jul 15, 2017 at 0:40
• link - for those who needed a quick reminder of the divisions like myself Jul 17, 2017 at 17:19

• This answer shows weak NP-hardness of the problem described in the question. I would also be interested to know whether this problem is strongly NP-hard. That is, if the input consists of a graph $G$, nodes $s$ and $t$, and integer weights for the edges written in unary, is the problem still NP-hard? Jul 11, 2017 at 3:08