Combinatorial algorithms face limits in dynamic max flow updates
A Note on the Hardness of Partially Dynamic Max Flow
Data Structures and Algorithms
Summary
Finding the maximum flow in a network is important for things like traffic or data routing. The authors studied how quickly algorithms can update these max flow values when the network changes a bit over time. They found a mathematical reason that certain types of algorithms can’t do this updating much faster than just recalculating from scratch in dense networks. This means efforts to speed up these updates for these algorithms likely won’t improve beyond a certain point.
What this means in practice
- •For network system designers: Understand limitations on speeding up max flow updates in dynamic networks for routing and load balancing.
- •For software engineers working on graph algorithms: Know that recomputing max flow fully after each update is near optimal for combinatorial methods in dense graphs.
A theory result. No direct application yet.
Authors
Thatchaphol Saranurak, Benyu Wang
Abstract
We study the fine-grained complexity of partially dynamic max flow in capacitated graphs. Assuming the combinatorial 4-clique hypothesis, combinatorial algorithms require $Ω(n^{2-o(1)})$ amortized update time. Thus, recomputing max flow after each update is optimal up to subpolynomial factors for combinatorial algorithms in dense graphs. The previous conditional lower bound was $Ω(n^{1-o(1)})$ amortized update time under SETH or the OMv hypothesis and applies to all algorithms [Dah16].