{"id":"arxiv:2511.02214","kind":"preprint","title":"Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching","authors":["Matija Bucić","Zhongtian He","Shang-En Huang","Thatchaphol Saranurak"],"author_count":4,"year":2025,"published":"2025-11-04","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2511.02214","nct_id":null,"source_url":"https://arxiv.org/abs/2511.02214","archive_url":"https://space-kitty.com/papers/arxiv:2511.02214","updated":"2025-11-04","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2511.02214","abstract":"We design efficient deterministic algorithms for finding short edge-disjoint paths in expanders. Specifically, given an $n$-vertex $m$-edge expander $G$ of conductance $φ$ and minimum degree $δ$, 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)/φ$ and in $mn^{1+o(1)}\\min\\{k, φ^{-1}\\}$ total time, assuming $φ^3δ\\ge (35\\log n)^3 k$, or (2) each of length at most $n^{o(1)}/φ$ and in total $m^{1+o(1)}$ time, assuming $φ^3 δ\\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 \\emph{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).","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}