Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now
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 ...


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.


1

I think it is possible to reason backwards from an optimal solution$^1$ to the order in which the paths have to be augmented to not have any pushing-back: In the solution, for any path from the source to the sink, where the flow is larger than zero, there is at least one edge, that constrains that flow, i.e: its flow is at capacity. If it were not, there ...


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