# 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

## 1 Answer

You can reduce Subset Sum to your problem.

Rough idea: Connect s,t with chain of double edges corresponding to weights and zero. A path from s to t picks a subset. These double edges can be expanded with dummy nodes to make a normal graph. To ensure non-empty subset make n chains to t with initial single edge corresponding to weight.

• 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
• When labels of edges are given in unary, the problem becomes NL-complete. I think the oldest reference is 'Valiant, Leslie G., and Michael S. Paterson. "Deterministic one-counter automata." Journal of Computer and System Sciences 10.3 (1975): 340-350', but it has been shown several times ever since. – Christoph Haase Jul 11 '17 at 10:09