Expander decompositions are well-established as a central tool in undirected graph algorithms, facilitating an avalanche of breakthrough results over the past two decades. Recently they have also found a home in directed graph algorithms, powering recent breakthroughs in max flow and dynamic shortest path.
In this talk, I discuss recent work advancing the state of the art of directed expander decompositions. I'll describe techniques from the undirected setting and discuss how to extend them to the directed setting to achieve a faster directed algorithm. Our methods are gardening-inspired: turning a hedge into a neat and tidy row of bushes turns out to be just like finding an expander decomposition!
Based on arXiv:2507.09729. Joint work with George Li and Jason Li.