This course studies modern graph algorithms through the lens of graph decomposition.
Over the last two decades, expander decompositions and hierarchies have become some of the most powerful tools for designing fast algorithms for connectivity, cuts, flows, and sparsification problems. However, the literature is quite scattered and technically heavy.
This course aims to make these main ideas unified, intuitive, and usable.
Recommended background: a first graduate algorithms course, familiarity with flows/cuts, and mathematical maturity
This course has 5 parts
Expander decompositions and hierarchies are one of the most powerful tools in designing graph algorithms in the last two decades. There are many variants of them in the literature, and it can be hard to navigate.
Here, we present a unified treatment and their immediate applications. With the right notations, there are just three main objects: Expander Decomposition, Separator-Expanding Hierarchy, and Boundary-Separator-Expanding Hierarchy. The algorithms for showing their existence are very simple.
Expander decomposition with applications to cut edge-sparsifiers (Lecture 2)
Boundary-linked expander decomposition with applications to flow vertex-sparsifiers (Lecture 3-4)
Equivalence of cut expansion and flow expansion (Lecture 5)
Two variants of expander hierarchies
Separator-expanding hierarchy with application to connectivity oracles under edge failures (Lecture 6).
Boundary-separator-expanding hierarchy with applications tree flow sparsifiers (Lecture 7)
In many applications, we need to construct expander decompositions and hierarchies fast. The tool underlying most of fast algorithms is called the cut-matching game. But the standard version of cut-matching game is actually not sufficient for state-of-the-art algorithms.
Here, we learn both the basic and advanced versions of the cut-matching game.
Basic cut-matching game (Lecture 8-9)
Non-stop versions of cut-matching game
Cut-matching game with deletions (Lecture 10)
Cut-matching game with deletions and vector transfers (Lecture 11)
Here, we learn how to combine the cut-matching games together with max-flow subroutines to construct expander decompositions and hierarchies in almost-linear time.
Our presentation here is usually much simpler and clearer than the corresponding papers in the literatures (as we assume the black box max-flow subroutine).
Structure of max-flow and min-cut (Lecture 12)
Approximate sparsest cut in max-flow time via basic cut-matching game (Lecture 13)
Separator-expanding hierarchy in max-flow time via cut-matching game with deletions and vector transfers (Lecture 14)
Expander decomposition and expander trimming in max-flow time via cut-matching game with deletions (Lecture 15)
Boundary-separator-expanding hierarchy via boundary-linked expander decomposition (Lecture 16)
Tree flow sparsifiers in max-flow time (Lecture 17)
Interlude: Survey of the recent development (Lecture 18)
The second half of the course aims to obtain fast algorithms without assuming the black box max-flow subroutine. Push-relabel has been one of the most versatile frameworks for this.
Here, we give a gentle introduction to push-relabel. We give a physical intuition of the process (gravity pulling strings). This process simultaneously captures both dynamic shortest path algorithms and push-relabel algorithms. To my best knowledge, this unification is novel and likely provide more intuition to both algorithms.
Dynamic shortest paths
Exact (Lecture 19)
Faster approximation on DAGs (Lecture 20)
Max flows via push-relabel
Exact (Lecture 21)
Faster approximation on DAGs (Lecture 22)
Here, we advanced the tools we learned further and finally obtain fast algorithms for expander decomposition and max flow (without assuming the black box max-flow subroutine).
Expander decomposition
Approximate sparsest cut via bounded-height push-relabel (Lecture 23)
Expander decomposition and trimming via dynamic push-relabel (Lecture 24-25)
Approximate max-flow
Multiplicative weight updates and tree flow sparsifiers (Lecture 26)
Exact max-flow
Separator-expanding hierarchy in directed graphs (Lecture 27)
Flow shortcut via separator-expanding hierarchy (Lecture 28)
Approximate maximum short flow via relabel-aggressive push-relabel (Lecture 29)
Leaky expander decomposition and hierarchy: simpler and faster constructions (Lecture 30)
Putting everything together (Lecture 31)
Beyond this course (Lecture 32)