Mincut upstream and downstream classification

Question

Came across this question while preparing for finals exams.

Suppose you’re looking at a flow network G with source s and sink t. We can classify the nodes into 3 categories.

We say a node v is upstream if, for all minimum s-t cuts (A,B), v is in A.

We say a node v is downstream if, for all minimum s-t cuts (A,B), v is in B.

We say a node v is central if it is neither upstream nor downstream; we can find a mincut where v is upstream, and another mincut where v is downstream.

Task: Give an algorithm that takes a flow network G and classifies each of its nodes as being upstream, downstream, or central. The running time of your algorithm should be within a constant factor of the time required to compute a single maximum flow.

It is quite difficult to classify a node as upstream or downstream, so my approach is to find all central nodes. I can do this for a single node u, I first find the max flow m on G, which corresponds to the mincut. Suppose u is in the s-component of this mincut; I then add an edge of negligible capacity from u to sink t, and find the mincut again. If the mincut remains the same, then there must be some other mincut where u is downstream, and so u is a central node. Conversely, if mincut increases, then I know that u is upstream. (To add an edge of neglibigle capacity, I scale everything up by some factor, such as |E|, and then add an edge of cap 1.)

The main difficultly using this method is I can't see a way to compute this for all nodes at once, hence I can't get the solution in a constant number of mincut runs.

The other possibility is given the max flow on the network, there might be a way to compute the minimal mincut and proceed from there.

Am I on the right track? Any hints are much appreciated!

Answer 1

You're correct about proceeding from the max flow.

Run say the Fork-Fulkerson algorithm G on the flow network. Say it returns with flow f*, and the residual graph is G_f*. Let U be the set of nodes that can be reached from the source s in G_f*. Then U is precisely the set of upstream nodes.

It is easy to see that all upstream nodes are in U: indeed, (U, V\U) is min-cut with U containing the source, so any upstream node must by definition belong to U in particular.

To see that all nodes in U are upstream, suppose for a contradiction that there is some node u in U that is not upstream. That is, there is a min-cut (A, B) with u in B. Consider the flow network G' obtained by adding an edge (u, t) with capacity 1 to G. Then the cut (A, B) has the same capacity in G' as in G since the added edge does not cross the cut, so min-cut(G') ≤ min-cut(G). On the other hand, we can send an additional unit of flow by following an s->u path in G_f* and then using (u, t), so max-flow(G') ≥ max-flow(G) + 1 > max-flow(G). Well, now by strong duality in G, min-cut(G') ≤ min-cut(G) = max-flow(G) < max-flow(G'), but this contradicts the weak duality in G'. Thus all nodes in U must be upstream.

(Note that we are only adding this edge hypothetically for the sake of the proof -- it is not part of the actual algorithm!)

By a symmetric argument, D = {v in V | there is a v -> t path in G_f*} is precisely the set of downstream nodes. The central nodes are then S \ (U union D).

The algorithm computes a single maximum flow, and uses two BFS's (one with the edges reversed) to compute the sets U and D, so the running time is okay.