Notes on ensuring Maximum Energy Flow using s-t flow/cut & residual graph

Maximum Flow problem is one of the important problems in combinatorial optimization. It finds feasible solution for flowing energy from one source to another point. Here we are interested to find a minimum energy labeling in a MRF.

Lets define our problem space using directed graph. Every edge denotes a flow and every flow has a capacity (black numbers in diagram) that it can hold. Each time when we make an energy flow we will mark it in the graph in red and obviously it have to be less than the capacity. The excess energy is the difference between incoming and outgoing values. For example E(v1)=1-(4+3)=-6. We can also compute excess energy for a set of veteces, E({v1,v2}). Now we need to consider v1 and v2 as a block and the difference between incoming and outgoing edges must be calculated.  E({v1,v2})=10+1 -(3)=8. We will also get the same result if we compute E(v1) and E(v2) separately and sum them up.flow
Now we will try to explain S-t flow. The main property of a S-t flow is that all the vertice other than source or drain must have an equal value of input and output.
s-t cut is a way where we separate the graph in two parts in such a order that source and drain goes into the second part and then we find the output capacity difference of it.
s-t flow can also be represented in term of s-t cut. In terms of s-t flow all other vertices excess energy of 0. So basically the value of flow for s-t flow=E(s) which is similar to write E(s)-E(v) so it is actually an s-t cut.  E(s)-E(v) can’t exceed the capacity.
To solve maximum flow, we can use Residual Graph. Resudual Graph is an undirected graph. In this undirected graph we would remove every edge when it gets saturated in other word we would keep edge of all the graph which has edge less than capacity. So whats our stopping condition? Eventually we will reach to a state where our sink will lose all its edge so its a state where we can’t reach in the end.
So we have got the maximum flow for the capacity of that. From the max value min cut theorem we can say that it would give us the minimum cut.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s