  In this work, we present the first algorithm to compute expander
decompositions in an $m$-edge directed graph with near-optimal time
$\tilde{O}(m)$. Further, our algorithm can maintain such a decomposition in a
dynamic graph and again obtains near-optimal update times. Our result improves
over previous algorithms of Bernstein-Probst Gutenberg-Saranurak (FOCS 2020),
Hua-Kyng-Probst Gutenberg-Wu (SODA 2023) that only obtained algorithms optimal
up to subpolynomial factors. At the same time, our algorithm is much simpler
and more accessible than previous work. In order to obtain our new algorithm,
we present a new push-pull-relabel flow framework that generalizes the classic
push-relabel flow algorithm of Goldberg-Tarjan (JACM 1988), which was later
dynamized for computing expander decompositions in undirected graphs by
Henzinger-Rao-Wang (SIAM J. Comput. 2020), Saranurak-Wang (SODA 2019). We then
show that the flow problems formulated in recent work of Hua-Kyng-Probst
Gutenberg-Wu (SODA 2023) to decompose directed graphs can be solved much more
efficiently in the push-pull-relabel flow framework.
