20
$\begingroup$

We know that computing a maximum flow resp. a minimum cut of a network with capacities is equivalent; cf. the max-flow min-cut theorem.

We have (more or less efficient) algorithms for computing maximum flows, and computing a minimum cut given a maximum flow is neither hard nor expensive, either.

But what about the reverse? Given a minimum cut, how can we determine a maximum flow? Without solving Max-Flow from scratch, of course, and preferably faster than that, too.

Some thoughts:

  • From the minimum cut, we know the maximum flow value. I don't see how this information helps the standard approaches augmenting-path and push-relabel, although adapting the latter seems slightly more plausible.

  • We can not use the minimum cut to split the network in two parts and recurse since that won't shrink the problem in the worst case (if one partition is a singleton); also we would not have a minimum cut of the smaller instances.

  • Does knowing the value of the maximum flow speed up solving the Max-Flow LP, maybe via the complementary slackness conditions?

Improve this question
$\endgroup$
4
  • $\begingroup$ Related question: do we know algorithms for computing min-cuts (that don't use max-flow algorithms)? $\endgroup$
    – Raphael
    Commented Dec 3, 2014 at 17:20
  • 3
    $\begingroup$ We definitely do, Karger's randomized algorithm is a very popular one, and you need zero knowledge of max-flows for that. $\endgroup$
    – Juho
    Commented Dec 3, 2014 at 17:25
  • 2
    $\begingroup$ If you don't want randomized algorithms, the Stoer-Wagner algorithm is a very simple one, also with no flow techniques. $\endgroup$
    – Juho
    Commented Dec 3, 2014 at 17:28
  • 2
    $\begingroup$ Good stuff! There's another challenge here. Knowing the min-cut conveys only $|V|$ bits of information (at most), since every cut is isomorphic to a subset of $V$. However, a max flow can need a lot more than $|V|$ bits of information to represent (especially if the capacities are large). So, information-theoretically, you can't hope for an algorithm that looks only at the cut and spits out the flow; it'd need to also look at the graph, too, and do some additional computation. (I realize this is not much of a barrier.) $\endgroup$
    – D.W. ♦
    Commented Jun 10, 2015 at 18:50

2 Answers 2

Reset to default
9
$\begingroup$

In the worst case, the minimum cut itself doesn't convey much information about the maximum flow. Consider a graph $G=(V,E)$ in which the minimum $s,t$-cut has value $w$. If I extend $G$ by adding a new vertex $s'$ and an edge $(s',s)$ with weight $w$, a minimum $s',t$-cut in the new graph consists of just the edge $(s', s)$ but that doesn't give any information about how to get $w$ units of flow from $s$ to $t$.

Effectively, the minimum cut tells you the value of the flow, but not how to achieve that flow. This means that knowing the minimum cut can speed up finding the flow by at most a logarithmic factor, since we could do binary search to find the value of the cut.

Improve this answer
$\endgroup$
1
  • $\begingroup$ But that logarithmic factor would be on the size of the interval of potential flow values, hence incomparable to the existing upper bounds on solving max-flow which only depend on the graph size. That said, even a logarithmic speedup would be of interest. I'm not convinced that knowing the value of a max-flow does not help at all. $\endgroup$
    – Raphael
    Commented Apr 16, 2016 at 11:19
-2
$\begingroup$

There certainly exist algorithms that let you compute the min cut before computing the maxflow. Two such algorithms are the push relabel and the pseudoflow algorithms which are closely related. The latter is more efficient. Both of these algorithms use special properties of the residual graph they iteratively improve to derive the maxflow from the min cut. For details I highly recommend reading the code and papers.

To elaborate on the push relabel case, when the algorithm can push no more flow to the sink it is guaranteed to have computed a min cut. This part of the algorithm is called phase 1 for lack of a better name. Phase 2 is the more efficient stage where it transforms the min cut into a maxflow by iteratively cancelling cycles in the residual graph using a single depth first search and pushing excess back to the source. I believe phase 2 can be proven to be asymptomatically more efficient than phase 1.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ Please re-read the question; it's not the one you answered. $\endgroup$
    – Raphael
    Commented Apr 17, 2019 at 5:58
  • $\begingroup$ The example of PR I gave assumes you have computed other information along the way while you were computing min-cut. Your original question did not specify if you were allowed to maintain other information along with the min-cut to make the subsequent maxflow calculation easier. Is it fair to state your original question as "Given a minimum cut and no other information, how can we determine a maximum flow?". $\endgroup$
    – ldog
    Commented Apr 17, 2019 at 8:03
  • 2
    $\begingroup$ I stated, "given A, compute B". The only reasonable assumption is that you are given only A, otherwise talking about computational problems would be a very fuzzy affair. $\endgroup$
    – Raphael
    Commented Apr 17, 2019 at 8:27
  • $\begingroup$ I beg to differ. From a practical perspective, you would never compute a min-cut without computing additional information (such as that in the PR algorithm.) From a theoretical perspective it might be nice to consider things in isolation as you say. Context is key here. $\endgroup$
    – ldog
    Commented Apr 17, 2019 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.