-1
$\begingroup$

Probelm: Deciding whether a network flow graph has more than one min cut.

Optimal running time: O(V^2*E).

I trying to prove the correctness of the next algorithm: run Dinitz to find max-flow and build the residual graph. One min cut will be all the vertices reachable from s (as T will be all other vertices) and second min cut will be all vertices reachable from t in the reverse graph. If both cuts are equal, than there is only one min cut. Otherwise, there are more.

I'm struggling proving this algorithm. I cannot find a reason for ensuring that I'll find another min cut if it exists. I tried to prove a lemma saying that a network flow graph has a unique minimum cut, iff each vertex is reacable from s or t in the residual graph. But I'm stuck proving the <= direction.

Improve this question
$\endgroup$
16
  • $\begingroup$ possible duplicate of Does Ford-Fulkerson always produce the left-most min-cut $\endgroup$
    – D.W. ♦
    Commented Jun 5, 2015 at 4:34
  • $\begingroup$ This is not a duplicate, I need a formal prove, which I cannot find. $\endgroup$
    – Danielyag23
    Commented Jun 5, 2015 at 5:26
  • 1
    $\begingroup$ What have you tried and where did you get stuck? (Also, keep in mind that nobody here is obligated to give you a full, formal proof. A proof roadmap may be the best you can get.) $\endgroup$
    – Raphael
    Commented Jun 5, 2015 at 5:59
  • $\begingroup$ I'll let others judge if it's a dup. You asked "how do I know that the first method is correct?" The results at the link I gave immediately yield a satisfying answer to your question. It has all the ideas needed for you to write your own full, formal proof. Work through the details there, then try seeing what you can come up with on your own. If you're still stuck edit the question to show us your attempt and what you're stuck with; if that's enough for you to figure it out, you can accept the duplicate or write up the full formal proof and list it as a self-answer to this question. $\endgroup$
    – D.W. ♦
    Commented Jun 5, 2015 at 6:19
  • $\begingroup$ Raphael - I thought about proving a lemma: in a network flow graph, there is unique minimum cut if and only if in the residual graph of the maximum-flow, each vertex is reachable from s or t (by reversing the edges). I can prove one side, by saying that if there is at least one vertex that is not reachable from both s and t, then by finding all reachable vertices from s in the first time and from t in the second time, I will receive two different minimum cuts, in contrary to the assumption that there is only one. But I can't prove the other side, I'm stuck. $\endgroup$
    – Danielyag23
    Commented Jun 5, 2015 at 6:51

1 Answer 1

Reset to default
2
$\begingroup$

The reason you can't prove your proposed algorithm correct is because.... it actually is not a correct algorithm for this problem. If you try running it on a small example of network flow graph with more than one unique min cut, you'll see immediately what goes wrong. In particular, this algorithm fails on every flow graph that contains more than one min cut, so the problem is not at all subtle.

Perhaps it would be helpful for you to recall properties of the min-cut that is produced by applying the min-cut/max-flow theorem to the flow output by a max-flow algorithm. In particular, define $S$ to be the set of vertices reachable from $s$ along some path in the residual graph, and $T$ to be the set of vertices that can reach $t$ along some path in the residual graph. Then $S \cap T = \emptyset$ and $S \cup T = V$, and $(S,T)$ is a $(s,t)$-cut. In particular, $(S,T)$ is the cut that is selected by the min-cut/max-flow theorem (for this flow). Good.

Now notice that $T$ is exactly the set of vertices that are reachable from $t$ in the reverse of the residual graph. Therefore, your proposed algorithm amounts to finding a max-flow, computing the sets $S$ and $T$, then checking whether $S$ and $T$ are the same cuts. But the only way to interpret $S$ as a cut is as the cut $(S,V\setminus S)$, and the only way to interpret $T$ as a cut is as the cut $(V\setminus T, T)$ -- and these are always exactly the same cut! In particular, $V \setminus S = T$ and $V \setminus T = S$, so both of these cuts will always be exactly the same cut -- even if the flow graph admits multiple different cuts, your procedure will only find one of them.

In short, your proposed lemma is wrong, and the method you suggest is not a correct algorithm for this problem. The good news is that it is possible to build a correct algorithm for this problem, within the running time that you specify; see my comments for more about how to do that -- but since you said in the question you don't want some other algorithm for this task, you just want to know if your proposed algorithm is correct, I won't try to elaborate in any further depth.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I still don't understand why the my algorithm fails, but let us leave it. Can you explain the formality of your solution? I realized that if I can define cuts by location, then I can compare left most min cut with right most min cut. But I don't understand the definition of "left-most min-cut"... $\endgroup$
    – Danielyag23
    Commented Jun 10, 2015 at 5:59
  • $\begingroup$ @user3680924, 1. If you don't understand why it fails, I encourage you to pick an example graph with two or more min cuts, run your algorithm on it (by hand), and add this to the question (add the graph & add the results you get). 2. My answer does not refer to the concept "left-most min-cut", but if you want to know the definition, see the links I gave you earlier in the comments (cs.stackexchange.com/q/42960/755 and stackoverflow.com/q/29418244/781723) -- in particular, if $(S_1,T_1),\dots,(S_n,T_n)$ are a list of all min-cuts, the left-most is $(\cap_i S_i, \cup_i T_i)$. $\endgroup$
    – D.W. ♦
    Commented Jun 10, 2015 at 18:30

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.