Fast Algorithms for Hop-Constrained Flows and Moving Cuts

Hop-constrained flows and their duals, moving cuts, are two fundamental quantities in network optimization. Up to poly-logarithmic factors, they characterize how quickly a network can accomplish numerous distributed primitives. In this work, we give the first efficient algorithms for computing $(1 \pm \epsilon) $-optimal $h$-hop-constrained flows and moving cuts with high probability. Our algorithms take $\tilde{O}(m \cdot \text{poly}(h))$ sequential time, $\tilde{O}(\text{poly}(h))$ parallel time and $\tilde{O}(\text{poly}(h))$ distributed CONGEST time. We use these algorithms to efficiently compute hop-constrained cutmatches, an object at the heart of recent advances in expander decompositions.