<p>You can reduce Subset Sum to your problem.</p>

<p>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.</p>

CC BY-SA 3.0
2017-07-11T03:08:42.187Z
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
CC BY-SA 3.0
2017-07-11T10:09:38.827Z
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
CC BY-SA 3.0
2017-07-10T20:15:13.117Z
2017-07-10T20:31:10.933Z
2017-07-10T20:31:10.933Z
Tomoki
<p>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. </p>

<p>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. </p>

<p>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. </p>

CC BY-SA 3.0
2017-07-10T20:00:09.593Z
Why do you think the problem is in NP? After all, the solution path (the certificate) can have potentially unbounded length.
Mikhail Rudoy
CC BY-SA 3.0
2017-07-10T20:01:45.747Z
Why do you think the problem is in NP? After all, the solution path (the certificate) can have potentially unbounded length.
Mikhail Rudoy
CC BY-SA 3.0
2017-07-15T00:40:29.153Z
Showing NP-hardness of this and relate problem is an exercise I often give when teaching reductions.
Neal Young
CC BY-SA 3.0
2017-07-17T17:19:31.040Z
[link](https://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/300px-P_np_np-complete_np-hard.svg.png) - for those who needed a quick reminder of the divisions like myself
David
<graph-algorithms><np-hardness>
Does a weighted graph have a path with weight zero?
user46034
# Does a weighted graph have a path with weight zero?

(Asked by: username_0 on 2017-07-10)

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.

**Tags:** graph-algorithms, np-hardness
> **Comments:**
> **username_1**: Why do you think the problem is in NP? After all, the solution path (the certificate) can have potentially unbounded length.  
> **username_1**: Why do you think the problem is in NP? After all, the solution path (the certificate) can have potentially unbounded length.  
> **username_2**: Showing NP-hardness of this and relate problem is an exercise I often give when teaching reductions.  
> **username_3**: [link](https://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/300px-P_np_np-complete_np-hard.svg.png) - for those who needed a quick reminder of the divisions like myself  

---

## 1 answers

### Answer by username_4 on 2017-07-10. Score: 3

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.

> **Comments:**
> **username_1**: 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?  
> **username_5**: 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.  

---

