20
$\begingroup$

Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut. Therefore, the complexity of computing a minimum $(s,t)$-cut is no more than the complexity of computing a maximum $(s,t)$-flow.

Could it be less? Could there be an algorithm for computing a minimum $(s,t)$-cut that is faster than any max-flow algorithm?

I tried finding a reduction to reduce the $(s,t$)-max-flow problem to the $(s,t)$-min-cut problem, but I wasn't able to find one. My first thought was to use a divide-and-conquer algorithm: first find a min-cut, which separates the graph into two parts; now recursively find a max-flow for the left part and a max-flow for the right part, and combine them together with all of the edges crossing the cut. This would indeed work to produce a maximum flow, but its worst-case running time might be as much as $O(|V|)$ times as large as the running time of the min-cut algorithm. Is there a better reduction?

I realize the max-flow min-cut theorem shows that the complexity of computing the value of a max-flow is the same as the complexity of computing the capacity of a min-cut, but that's not what I'm asking about. I'm asking about the problem of finding a max-flow and finding a min-cut (explicitly).

This is very closely related to Compute a max-flow from a min-cut, except: (1) I'm willing to allow Cook reductions (Turing reductions), not just Karp reductions (many-one reductions), and (2) perhaps given $G$ we can find some graph $G'$ such that the min-cut of $G'$ makes it easy to compute the max-flow of $G$, which is something that's out of scope for that other question.

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ @AshkanKzme, I'm not following you; can you elaborate? As I state in the 4th paragraph of the question, the max-flow min-cut theorem shows that the value of the max-flow is equal to the capacity of the min-cut. I suspect this is what you are thinking of. However, knowing the value of the max-flow doesn't tell you the max-flow itself (e.g., how much to send on each particular edge). This question is asking about the complexity of computing the max-flow itself, vs of computing the min-cut itself. My question is exactly as stated in the 2nd paragraph of the question. $\endgroup$
    – D.W. ♦
    Jun 12, 2015 at 4:22
  • 2
    $\begingroup$ @AshkanKzme, No, I made no wrong assumption. You are implicitly assuming that Ford-Fulkerson is the fastest possible algorithm for finding a min-cut... but as far as I know, no one has ever proven that, and we don't know whether that's correct or not. It sounds to me like you're making the standard rookie mistake with lower-bound proofs: "I can't see any way to solve this problem faster, so it must be impossible". (P.S. You're telling me standard textbook stuff about max-flow min-cut. I appreciate your attempt to help, but I'm already familiar with that...) $\endgroup$
    – D.W. ♦
    Jun 12, 2015 at 8:08
  • 1
    $\begingroup$ As far as your statement "I think it can be proved that if you have only the min-cut, you can get the maximum flow", well, I encourage you to write an answer with the proof of that -- because that's basically what my question is asking. I've never seen a proof of that, but if you have, I hope you will write it up! $\endgroup$
    – D.W. ♦
    Jun 12, 2015 at 8:12
  • 1
    $\begingroup$ @D.W. I think I get the question a little better now. I think I was put of by the fact you give a polynomial turing reduction. Wouldn't you need a constant turing reduction to prove $f(n) = \Theta(g(n))$, while even proving there is no such reduction possible does not disprove it? $\endgroup$
    – Thomas Bosman
    Jun 17, 2015 at 18:48
  • 1
    $\begingroup$ @ThomasBosman, yes, that's correct. [Sorry for confusing you. The reduction I gave in the question proves that $f(n) = \Omega(g(n)/n)$, which is a very weak lower bound. I'm hoping there might be a reduction which proves that $f(n) = \Omega(g(n))$, but I don't know how to construct such a thing.] $\endgroup$
    – D.W. ♦
    Jun 17, 2015 at 19:01

1 Answer 1

Reset to default
-1
$\begingroup$

Here is a possible approach:

Suppose you know the cut S, then finding the flow from $S$ to $t$ is a min cost network flow problem with zero cost, since you know exactly the outflow at each vertex in $V\setminus S$ and in the inflow at $t$. Suppose $f$ denotes an $S-t$ flow and $A$ the node-arc matrix (i.e. row $i$, col $j$ has 1 if $i$ is the tail of $j$, -1 if its the head, zero otherwise), and let $b$ be such that $Af = b$ if $f$ satistfies the supply/demand, and the flow conservation. Then with gaussian elimination we can find a feasible solution in $|V|^3$ operations.

To find a cut from a flow we need to construct the residual graph which takes at most $|E|$ time, and then potentially traverse $|V|$ vertices.

So for complete graphs and the minimum cut being just the source or just the sink, the reduction takes equal time in both directions worst case. However, I would think that finding a feasible solution to $Af =b$ can be done faster than $|V|^3$ given the special structure. I am not sure how to prove that though.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I don't understand how to find $f$ using Gaussian elimination. We have $|V|$ linear equations in $|E|$ unknowns. Usually $|E|>|V|$, so we won't have enough equations to uniquely determine the unknowns. Is there a trick I'm overlooking? $\endgroup$
    – D.W. ♦
    Jun 19, 2015 at 3:21
  • $\begingroup$ I'm not an expert on this either, so I may be wrong. But the fact that there is no unique solution seems to make it easier. If you reduce it to row reduced echelon form, you have $|V|$ independent columns. Then the unique solution of that submatrix and $b$, combined with zero flow for all the other columns would yield a non unique solution, which is not a problem per se. The problem I can foresee is that $f$ violates the capacity constraints, But intuitively I'd say there is a way to circumvent this directly $\endgroup$
    – Thomas Bosman
    Jun 19, 2015 at 3:47
  • $\begingroup$ Yeah, the capacity constraints seem like the key challenge. Otherwise, solving the system of linear equations might give you a solution that satisfies $Af=b$ but is not a valid flow because it violates the capacity constraints. $\endgroup$
    – D.W. ♦
    Jun 19, 2015 at 3:53
  • $\begingroup$ Crap that's right. You could add the constraints (upper and lower), which you know has a solution, but then you have |V|+2|E| rows so that would be slower then just calculating the max flow directly. $\endgroup$
    – Thomas Bosman
    Jun 19, 2015 at 16:12
  • $\begingroup$ The other problem is that the capacity constraints are inequalities (not equalities), so you can't use Gaussian elimination: you'd need to use linear programming, which as you say doesn't seem likely to be any faster than just calculating the max flow directly. $\endgroup$
    – D.W. ♦
    Jun 19, 2015 at 16:33

Your Answer

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

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