This is perhaps one of my more favorite graph algorithms: max-flow min-cut. It’s probably one of the most elegant algorithms, yet practical and useful in so many areas. In this problem, I’m gonna talk a little about graph stability.
A flow graph G is called k-stable iff by changing the capacity on k edges in G the max-flow value doesn’t change. A very nice wording! By this you can tell that in a specific road network for example, changing only k edges just doesn’t do! No matter what you can do to the capacities of these k roads, traffic is still gonna be a nightmare, you’re not moving an inch towards a better solution!
Take the case when k=1. This means that you cannot get a better flow through the network by changing one edge. Any edge.
A straightforward solution to this is by performing a max-flow procedure, using any of the pretty well-documented algorithms, to obtain a residual network whose source is disconnected from the sink. You can do this in O(V²E) with a moderately complicated implementation. Afterwards, you can try to look for an edge such that if you increase its capacity (let’s call this edge-promotion!), the max-flow increases. If found, this means the graph is NOT 1-stable, in other words, it is 1-unstable. In order to prove it in fact is 1-stable, you have to exhaust all the options by trying all possible edges and making sure none of them can increase the total max-flow if promoted on its own. If you check using a BFS, this means a quadratic time to exhaust all the possibilities.
A better way to do this is by constructing two sets of vertices: those that are reachable from the source, call it Vs, and those that can reach the sink, call it Vt. Now it’s very easy to check in a linear time, by just checking each edge if it starts with a vertex in Vs and ends with a vertex in Vt. If we find such an edge, the graph is not 1-stable.
If we want to check for 2-stability, it gets a little more complicated, since now we need to find a path that contains two (consecutive?) edges which can increase the max-flow if promoted together. Surprisingly, we can still do this in a linear time. What we have to do now is split vertices into three sets: those that are reachable from the source (Vs), those that can reach the sink (Vt), and the rest of the vertices (Vm), which will lie in the middle, unreachable from any other vertex. Now the problem reduces to finding a path from the source to the sink that passes through two edges which used to be saturated. In fact, it is easier to just promote all the edges between those three sets and try to find a path, which is still a linear process.
Can we still do this with k>2?
Yasser Ebrahim 