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

New answers tagged


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\...


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.


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


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

Top 50 recent answers are included