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

Matija Bucić, Zhongtian He, Shang-En Huang +1

We design efficient deterministic algorithms for finding short edge-disjoint paths in expanders. Specifically, given an $n$-vertex $m$-edge expander $G$ of conductance $\varphi$ and mini…