The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

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. 4 Those answers assume that all edge capacities are integers. Assuming they are, this works. Suppose the min-cut in the original graph has total capacity$x$; then it will have total capacity$x(|E|+1)+k$in the transformed graph, where$k$counts the number of edges crossing that cut. Note that if you consider any cut in the original graph with larger ... 0 I will assume, that all weights are rational (since there is a problem with representing irrational numbers on computer). You can solve this problem by using linear programming in similar manner to finding maximal flow.$\forall_{v \in V} w_V$is constant.$\forall_{e \in E} w_e\$ is variable. Firstly, for each node we want to be sure that inward flow is ...