pipette
ESEspañol

A Note on the Hardness of Partially Dynamic Max Flow

Thatchaphol Saranurak, Benyu Wang

Preprint

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