# Max-Flow Min-Cut
Rough Notes

from an implemenation point of view, i'll have to make the edges as negative of their weights, since the problem here it to maximize flow. our problem is to minimize the total weights, so flipping the sign should work fine. i'll also have to take care of making all capacities >=0 for the algorithm to work. there is going to be some implementation eh meh.

### Basics
- otimization problem
- have to obey conservation laws, accumulation stuff.
- imagine the digraph as a flow network: G(V, E)
- source(s), sink/target(t) belong to V
- *accumulation* not allowed. Everything that enter has to leave (Kirchoff's Laws!). Except for s and t nodes.
- edges belong to E, have non-negative capacity. PROBLEM! solve? make everyone >=0
- if (u, v) doesnt belong to E, C(u, v) = 0. their capacity is zero
- can have cycles (problem?)
- there is some flow going for each edge. it can't exceed capacity; a local constraint.
- the sum of all flows of the edges of s are the same as that of t.
- the problem is challenging since decreasing the flow in certain regions locally will help to increase the flow globally. makes sense? bit counter intuitive.
- the above implies that sometimes we'll need to go back and correct our mistakes; and decrease the flow locally, increasing it globally. so, no Dijkstra OR Msts!

### Algorithm setup
- We disallow cycles of length 1
- We convert the cycles of length 2 into those of length 3 for our convenience. this will add some overhead in our algorithm, which I'll compare with the case when we don't do this conversion.
- For now, we convert cycles of length 2 into length 3, and then call the positive or net flow as just flow. We have to make this distinction incase we don't convert it.
- **Flow**: A function f on G st f: VxV -> R
- **Capacity**: for all u, v belonging to V, we have f(u, v) <= C(u, v)
- **Flow Conservation**: for all u, v in V - {s, t}, sum(f(u, v)) = 0
- **skew symmetry**: f(u,v) = -f(v, u)
- |f| = sum(f(s, v) = f(s, V)
- f(X, X) = 0
- f(x, y) + f(y, x) = 0
- f(X, Y) = -f(Y, X)
- f(X union Y, Z) = f(X, Z) + f(Y, Z) if (X intersect Y) = NULL
- Prove: f(s, V) = f(V, t)
- |f| = f(s, V)
- f(V, V) = f(V-s, V) + f(s, V) = 0 [disjoint, f(X,X) = 0]
- f(V-s, V) = -|f| = -f(V, V-s)
- |f| = f(V, V-s) = f(V, V-s-t) + f(V, t) [since V-s-t and t are disjoint]
- |f| = f(V, t) + 0 [conservation, intermediate sum to 0]
- Hence Proved! |f| = f(V, t) = f(s, V)
- **cut**: (S, T) is a partition of s belonging to S, and t to T. Both are disjoint sets. S can ba any size >= 1, and same for T. (doesnt require flow to be max)
- LEMMA: For ANY flow, and ANY cut (S, T), |f| = f(S, T). NOTE how it doesn't matter what nodes are in S and what nodes are in T. This ALWAYS holds.
- f(S, T) = f(S, V) - f(S, S) = f(S, V)
- f(S, T) = f(V, T) - f(T, T) = f(V, T)
- f(S, V) = f(S-s, V) + f(s, V) = f(s, V) [since there is no s or t in S-s.]
- f(S, V) = f(s, V) = |f| = f(V, T)
- The capacity of any cut bounds the current flow. Since we can find flows for any arbitary partitions, we now simply find the min-cut, which is the bottle-neck. Reframing it, the min-cut is one case when the capacity = flow. Makes Sense!
- **Residual Network**: local notion, saying there's still some flow left.
- Gf(V, Ef)
- a residual edge Cf(u, v) = C(u, v) - f(u, v) > 0 (if 0, we don't add the edge)
- edges with full capacity are not shown in resnet
- edges not in capacity show up with 2 edges: reverse and remaining.
- edges not used show up as 1 reverse edge
- Augmenting paths: if path from s to t exists, we can always add atleast 1 more unit of flow.
- Residual Capacity Cf(P): take the min of all the edge weights used to traverse the augmenting path(P).
- Cf(P) = min(Cf(u, v)) for all u, v

~~NOTE: Yet to do lecture 14, which i'll continue in tomorrow's 2H slot~~

### Algorithm: Ford Fulkerson
start with f(u, v) = 0 for all u and v

while augmenting_path(Gf):
    augment f by Cf(P)

Makes sense, but at the end, will it terminate? And if it does, if the flow the max?

The following are equivalent
1. |f| = C(S, T) for some cut (S, T) (the bottleneck cut)
2. f is maximum flow
3. f admits no augmenting paths

For the algorithm we need to prove 3->2.

Proving 1->2:
since |f| <= C(S, T), |f| = C(S, T) implies that |f| is the maximum, and can't be increased

Proving 2->3:
If an augmenting path exists, the flow can be increased. This contradicts the above, thus is not possible.

Proving 3->1:
So f doesnt admit more augmenting paths.
Now, we know

S = {u: for all u in Gf, there is a path form s to u}
T = V-S

s belongs to S
t belongs to T

Now, consider nodes u in S and v in T respectively. No edge from u to v in Gf, since if there wa, we would have included v in S.

Lets just say that u to v has an edge in G (the original). The only case when this happens is when the u -> v edge is saturated. Formally,

Cf(u, v) = 0 since if Cf(u, v) > 0, then v belongs to S, and not T. this is contradiction.
So, Cf(u, v) = 0

Thus, Cf(u, v) = C(u, v) - f(u, v) = 0
Thus, f(u, v) = C(u, v)

This means that that cut has reached full capacity.
summing over all u in S and v in T, f(S, T) = C(S, T)

Ford Fulkerson Killer

Solution: Edmonds Karp - BFS:

Shortest path counting the #edges
O(VE) worst case time complexity to find one augmenting path
O(VE^2) total complexity

[Edmons Karp Paper](https://web.eecs.umich.edu/~pettie/matching/Edmonds-Karp-network-flow.pdf)

Some others:
O(VE(log(V)/log(E/VlogV)))
O(VE) fast matrix multiplication