# Could min cut be easier than network flow?

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.

• @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. – D.W. Jun 12 '15 at 4:22
• @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...) – D.W. Jun 12 '15 at 8:08
• 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! – D.W. Jun 12 '15 at 8:12
• @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? – Thomas Bosman Jun 17 '15 at 18:48
• @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.] – D.W. Jun 17 '15 at 19:01

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.

• 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? – D.W. Jun 19 '15 at 3:21
• 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 – Thomas Bosman Jun 19 '15 at 3:47
• 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. – D.W. Jun 19 '15 at 3:53
• 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. – Thomas Bosman Jun 19 '15 at 16:12
• 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. – D.W. Jun 19 '15 at 16:33