Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching

We design efficient deterministic algorithms for finding short edge-disjoint paths in expanders. Specifically, given an \(n\)-vertex \(m\)-edge expander \(G\) of conductance \(\phi\) and minimum degree \(\delta\), and a set of pairs \(\{(s_i,t_i)\}_i\) such that each vertex appears in at most \(k\) pairs, our algorithm deterministically computes a set of edge-disjoint paths from \(s_i\) to \(t_i\), one for every \(i\): (1) each of length at most \(18 \log(n)/\phi\) and in \(mn^{1+o(1)} \min\{k,\phi^{-1}\}\) total time, assuming \(\phi^3 \delta \ge (35 \log n)^3 k\), or (2) each of length at most \(n^{o(1)}/\phi\) and in total \(m^{1+o(1)}\) time, assuming \(\phi^3 \delta \ge n^{o(1)} k\). Before our work, deterministic polynomial-time algorithms were known only for expanders with constant conductance and were significantly slower. To obtain our result, we give an almost-linear time algorithm for hypergraph perfect matching under generalizations of Hall-type conditions (Haxell 1995), a powerful framework with applications in various settings, which until now has only admitted large polynomial-time algorithms (Annamalai 2018).