1
$\begingroup$

We were given an exam question of: Given a flow network G=(V,E) with integer edge capacities, a max-flow f in G, and a specific edge e in E, design a linear time algorithm that determines whether or not e belongs to a min-cut.

From the grading rubric we are told a correct algorithm - I got dinged for not having the correct algorithm according to the rubric. I have flushed out my algorithm and can’t see why it is wrong. There are similar posts, but they all solve problem by running max-flow after adjusting e downwards, which is at best a polynomial algorithm O(mn) Orlin+KTR, and at worst pseudo-polynomial O(Cm) Ford-Fulkerson.

Here is rough description:

  1. Since have max flow, create residual graph Gf. O(m)

  2. Find the first min-cut by the normal method of BFS search for all nodes reachable by S in Gf. Check if edge e is in this cut. If it is in min-cut we are done.

  3. Since it was not in the min-cut, look for the next min-cut if there is one. Do this by modifying Gf by removing the nodes in the min-cut set and adding a forward edge from a new S to the nodes on the other side of the min-cut. That way the edges from the new S to the existing nodes on the other side of the min-cut will not be part of any min-cut.

  4. We then repeat 2 using this new graph which will find the next min cut.

  5. We stop when we can get to t, which at this point if edge not found then it is not in min-cut

Since we traverse the tree only once this is generally O(m), although in the modifications to Gf we may have to traverse a node twice (think a straight line graph with every edge being a minimum cut) so it is worst case O(m + 2m) -> O(m)

Gf_0

gf_1

Gf_2

Update:

After researching more (Does Ford-Fulkerson always produce the left-most min-cut), refining my claim that the above algorithm will find every edge e that is part of a min-cut (not every minimum cut which is exponential).

Looking at my example below, you will see that there are 4x4x4x4 = 256 minimum cuts in the graph, but only 4+4+4+4 = 16 edges that appear in a minimum cut.

many min cuts

Proof:

Let’s say that this algorithm misses an edge that is in a minimum cut. If this is the case, when we did a BFS in the residual graph we were able to traverse through that edge. But the only way BFS can traverse that edge would be if it has forward capacity, but since this is an edge in a minimum cut this is not possible, a contradiction. If we can reach the node on the other side of that edge during our BFS that also means that this edge can’t be part of a min-cut, which the algorithm would figure out.

Improve this question
$\endgroup$
5
  • $\begingroup$ Re-compute a max-flow after decreasing the capacity of an edge by 1 can be done by linear time. $\endgroup$
    – xskxzr
    Nov 16, 2018 at 3:28
  • $\begingroup$ Yes, not the question though, that is the accepted answer on the grading sheet. I.E. Reduce e by 1, reduce flow on s-t path through e, then look for new augmenting path. I'm trying to figure out if my alternative algorithm is correct. $\endgroup$
    – Scooter2000
    Nov 16, 2018 at 4:01
  • $\begingroup$ Please don't edit the question to add an answer. Instead, post an answer (yes, you can answer your own question). $\endgroup$
    – xskxzr
    Nov 17, 2018 at 3:58
  • $\begingroup$ Got it, although I was adding information to the question when I didn’t know the answer. In any event, I now know the answer to the question, should I post it, let others have a crack at solving it, or delete the question? $\endgroup$
    – Scooter2000
    Nov 17, 2018 at 19:40
  • $\begingroup$ Yes, you are welcome to post it as an answer. $\endgroup$
    – xskxzr
    Nov 18, 2018 at 3:09

1 Answer 1

Reset to default
2
$\begingroup$

Will not find A-E, B-C min-cut. Will find A-B, A-E and C-D. Graph does not show flow direction, but assume left to right (i.e. A->B, B->C, A->E, E->C and C->D) 

    B
   / \
1 /   \ 1
 /     \   2
A       C --- D
 \     /
1 \   / 4
   \ /
    E
Improve this answer
$\endgroup$

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.