A Note on the Hardness of Partially Dynamic Max Flow
In the authors' words
We study the fine-grained complexity of partially dynamic max flow in capacitated graphs. Assuming the combinatorial 4-clique hypothesis, combinatorial algorithms require 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 amortized update time under SETH or the OMv hypothesis and applies to all algorithms [Dah16].
Main resultThe abstract does not state a limitation.
Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: SOSA 2027