1
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mikhail Rudoy Jul 11 '17 at 3:08
  • 1
    $\begingroup$ 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. $\endgroup$ – Christoph Haase Jul 11 '17 at 10:09

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.