Reduction from OuMV to dynamic st-Maximum Flow

FROM: OuMV TO: dynamic st-Maximum Flow

Implications

assume: OMv
then: there is no algorithm for solving incremental (or decremental) st-max-flow on unweifghted directed graphs or weighted undirected graphs on $n$ nodes with amortized time $O(n^{1-\epsilon})$ per operation for any $\epsilon > {0}$

Year

2016

Reference

Dahlgaard, S. (2016). On the hardness of partially dynamic graph problems and connections to diameter. arXiv preprint arXiv:1602.06705.

https://arxiv.org/abs/1602.06705