Set of nodes in every minimum cut of flow graph

Question

I'm currently working through exercises to study network flow algorithms, and I'm stuck on a sub-problem I think is necessary to solve one such exercise.

The question: How does one compute the set of nodes which belong to every minimum cut of a flow graph?

Intuitively, if Ford-Fulkerson is used and augmentation paths are chosen so as to have a minimum number of edges, this should give us a cut set of minimal cardinality, but must these nodes be in every minimum cut?

If so, I can't seem to prove it. If not, I don't have any real ideas. Perhaps finding a mechanism for exchanging edges in the residual graph?

Answer 1

I believe I've cooked up an appropriate answer:

Claim: Every node which can be in a (source-side) min-cut set must be source-reachable in flow residual graph Gf returned by max-flow (i.e. Ford-Fulkerson).

Proof: Suppose not. Then, there exists some u such that there is no s-u path in Fg and is in some source-side min-cut set S'. Since F-F returns the set of nodes reachable by s as its min-cut set (e.g. by BFS), S' is not returned by F-F. This implies u is in T (the sink-side of the min-cut).

We now show that there is no means of transforming S to S' while retaining the min-cut property. Suppose it were possible. Then, any algorithm capable of the transformation would need to be able to identify an s-u path to push flow from s to u in some residual graph. Note, however, that this is not possible.

Consider any edge (v, w) such that v is in S and w in T. Since u was not in S, it must be that w is not u (i.e. there is no forward edge from S to u, else it would be in S already). Then, it must be that u is made accessible to s by adding a forward edge from S to T. However, this is impossible! Flow only may be added on reverse edges, by the max-flow/min-cut property. The claim is then proven.

To solve the problem posted above, we simply compute the set of all nodes which can be in a source-side min-cut set (call this set A), then reverse edges and compute the set of all nodes which can be in a sink-side min-cut set (call this B), compute the intersection (call this C), and then compute Answer = A - C. The complexity of this algorithm is the same as F-F, which is to say O(|V|^3).

Please let me know if you find any errors! Sorry for answering my own question!