How to linearize your cluster

[Lagrang3]

@sipa

That’s surprising to me, because if you computed the min-cut, in our setting, you know the closure, whose total fee and size you can determine in O(n)O(n)O(n) time (just sum them up), and the max flow of the problem you just solved will be \operatorname{fee} - \lambda \operatorname{size}fee−λsize\operatorname{fee} - \lambda \operatorname{size}, with \lambdaλ\lambda the parameter value you just solved for. So it seems to me that not computing the actual max flow can at best save you O(n)O(n)O(n) work.

One thing is the scalar value of the maximum flow (the sum of all incoming flows to the sink) and the flow function that achieves that value (real valued function over the set of edges). In the context of Goldberg-Tarjan algorithm when you arrive to a certain state for which every node with positive excess is unable to reach the sink, then you can already construct the min-cut and maxflow value with O(m), but this might be an incomplete state for the sake of the flow function cause the balance conditions are not guaranteed to be satisfied yet, you’re still at a preflow state and every excess flow has to go back to the source before a proper flow function is obtained.