A Cut-Matching Game for Constant-Hop Expanders

This paper extends and generalizes the well-known cut-matching game framework and provides a novel cut-strategy that produces constant-hop expanders.

Constant-hop expanders are a significant strengthening of regular expanders with the additional guarantee that any demand can be (obliviously) routed along constant-hop flow-paths -in contrast to the Ω(log n)-hop paths in expanders.

Cut-matching games for expanders are key tools for obtaining linear-time approximation algorithms for many hard problems, including finding (balanced or approximately-largest) sparse cuts, certifying the expansion of a graph by embedding an (explicit) expander, as well as computing expander decompositions, hierarchical cut decompositions, oblivious routings, multi-cuts, and multi-commodity flows.

The cut-matching game of this paper is crucial in extending this versatile and powerful machinery to constant-hop and length-constrained expanders [HHT24] and has been already been extensively used 1 . For example, as a key ingredient in several recent breakthroughs, including, computing constant-approximate k-commodity (min-cost) flows in (m + k) 1+ǫ time [HHL + 24] as well as the optimal constant-approximate deterministic worst-case fully-dynamic APSP-distance oracle [HLS24] -in all applications the constantapproximation factor directly traces to and crucially relies on the expanders from a cut-matching game guaranteeing constant-hop routing paths.