Reduction from OuMv to Bipartite Graph MCM

FROM: OuMv TO: Bipartite Graph MCM

Implications

assume: OMv
then: there is no algorithm for solving incremental (or decremental) maximum cardinality bipartite matching with amortized time $O(n^{1-\epsilon})$ per insertion (or deletion) and $O(n^{2-\epsilon})$ time per query 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