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).

In the 1960’s, Erdős and Gallai conjectured that the edges of any n-vertex graph can be decomposed into O(n) cycles and edges. We improve upon the previous best bound of O(n loglogn) cycles and edges due to Conlon, Fox and Sudakov, by showing an n-vertex graph can always be decomposed into O(n log⋆ n) cycles and edges, where log⋆n is the iterated logarithm function. Our arguments make use and further develop the theory of robust sublinear expander graphs.