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:
Since have max flow, create residual graph Gf. O(m)
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.
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.
We then repeat 2 using this new graph which will find the next min cut.
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)
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.
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.