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

2025/11/04 by Bucić, Matija, He, Zhongtian, Huang, Shang-En +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Quantum Computing Algorithms and Architecture

paper · doi:10.48550/arxiv.2511.02214

openalex publication_date 2025/11/04 · openalex created_date 2025/11/06 · openalex updated_date 2026/07/28

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 ϕ³δ≥ (35log n)³ k, or (2) each of length at most n^o(1)/ϕ and in total m^1+o(1) time, assuming ϕ³ δ≥ 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).

Citations

• Nearly Hamilton cycles in sublinear expanders, and applications
• Deterministic Expander Routing: Faster and More Versatile
• Edge-disjoint cycles with the same vertex set
• Minor Containment and Disjoint Paths in almost-linear time
• Edge-disjoint paths in expanders: online with removals
• A Cut-Matching Game for Constant-Hop Expanders
• Towards the Erdős-Gallai Cycle Decomposition Conjecture
• Separating paths systems of almost linear size
• Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic and Fast
• Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization
• The Combinatorial Santa Claus Problem or: How to Find Good Matchings in Non-Uniform Hypergraphs
• A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
• Expander Decomposition and Pruning: Faster, Stronger, and Simpler
• A Tale of Santa Claus, Hypergraphs and Matroids
• New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms
• Almost Polynomial Hardness of Node-Disjoint Paths in Grids
• Finding Perfect Matchings in Bipartite Hypergraphs
• Combinatorial Algorithm for Restricted Max-Min Fair Allocation
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Graph Clustering using Effective Resistance
• On Representatives of Subsets

Related

• Edge-disjoint paths in expanders: online with removals
• Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
• Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
• A Simple Deterministic Algorithm for Edge Connectivity
• Sublinear Time Shortest Path in Expander Graphs