Tag Info

Hot answers tagged network-flow

1

This problem is NP-hard if 0 weight is allowed. We can reduce Not-All-Equal 3SAT to the decision version of this problem. Given an instance of Not-All-Equal 3SAT with $n$ variables and $m$ clauses, for each variable $x_i$, we create two vertices $v_i$ and $v_i'$ with an edge between them for each variable. In addition, for each clause, for example, $x_1\... 1 Yes, you can. If it has, say, no outcoming edge, there can be no flow routed over this node. Otherwise the flow conservation constraint for this node ($v\$) $$\sum_{(u,v) \in E} f_{uv} - \underbrace{\sum_{(v,w) \in E} f_{vw}}_{= 0} = 0$$ is violated if you have incoming flow.

Only top voted, non community-wiki answers of a minimum length are eligible