Blocking Flows
6.854 Notes #10

David Karger

1 Last Time: Scaling

2 Blocking Flows

Extension of shortest augmenting path.
Dinic’s algorithm:

2.1 Blocking Flows in Unit-capacity Graphs

Wait a minute: This does not sound too impressive. We already knew how to do that! (Our first algorithm run in time \(O(mnU)\).) Why bother?

How to get a better bound for unit-capacities?

2.2 Blocking Flows in General Graphs

What breaks when we try the above analysis in general graphs?

2.3 Scaling Blocking Flows

Basic idea:

End result: Implementation of the blocking flow primitive in only \(O(m\log n)\) (instead of \(O(mn)\)) time. (\(O(\log n)\) overhead comes from the splay trees.)

\(\Rightarrow\) Gives an \(O(mn\log n)\) time algorithm!

3 Beyond Flow Decomposition Barrier