The Expander Hierarchy and its Applications to Dynamic Graph Algorithms

Understand

We introduce a notion for hierarchical graph clustering which we call the expander hierarchy and show a fully dynamic algorithm for maintaining such a hierarchy on a graph with $n$ vertices undergoing edge insertions and deletions using $n^{o(1)}$ update time.

• An expander hierarchy is a tree representation of graphs that faithfully captures the cut-flow structure and consequently our dynamic algorithm almost immediately implies several results including: (1) The first fully dynamic algorithm with $n^{o(1)}$ worst-case update time that allows querying $n^{o(1)}$-approximate conductance, $s$-$t$ maximum flows, and $s$-$t$ minimum cuts for any given $(s,t)$ in $O(\log^{1/6} n)$ time.
• Our results are deterministic and extend to multi-commodity cuts and flows.
• The key idea behind these results is a fully dynamic algorithm for maintaining a tree flow sparsifier, a notion introduced by R\"acke [FOCS'02] for constructing competitive oblivious routing schemes.