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

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].