Set of nodes in every minimum cut of flow graph

2
votes

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?

Please help!

1
algorithmnetworkingflow
"but must these nodes be in every minimum cut?" absolutely not. – n. 1.8e9-where's-my-share m.
Are you sure the problem talks about nodes? A cut is a subset of the edge set. – n. 1.8e9-where's-my-share m.
The optimal solution to Minimum cut of a graph is the same optimal solution to Maximum flow of the same graph – Khaled.K
As I understand it, a cutset can be defined just as well with nodes. For example, if we define A = {s} and B = V - {s}, then we implicitly define an s-t cut with capacity equal to the sum of the capacities of edges leaving/entering {s}. These are the types of cut-sets I am referring to above. – notwatson
@n.m. It relates to max-flow as follows: Consider some node set S, and some node set V - S. The arcs from S to V-S define the minimum capacity cut. This is the basis of Ford-Fulkerson, if we set S to be the set of nodes reachable from the source in the terminating residual graph. – notwatson

1 Answers

2
votes

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!