# 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. – Mikhail Rudoy Jul 10 '17 at 20:00
• Why do you think the problem is in NP? After all, the solution path (the certificate) can have potentially unbounded length. – Mikhail Rudoy Jul 10 '17 at 20:01
• Showing NP-hardness of this and relate problem is an exercise I often give when teaching reductions. – Neal Young Jul 15 '17 at 0:40
• link - for those who needed a quick reminder of the divisions like myself – David Jul 17 '17 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? – Mikhail Rudoy Jul 11 '17 at 3:08