pipette
ENEnglish

A Note on the Hardness of Partially Dynamic Max Flow

Thatchaphol Saranurak, Benyu Wang

Preprint

En palabras de los autores

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

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: SOSA 2027