Reduction from Directed, Weighted APSP to 2-sensitive decremental st-shortest paths

FROM: Directed, Weighted APSP TO: 2-sensitive decremental st-shortest paths

Implications

assume: APSP Hypothesis
then: target cannot be solved with preprocessing time $O(n^{3-\epsilon})$ and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected weighted graphs

Year

2017

Reference

Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems. arXiv preprint arXiv:1703.01638.

https://arxiv.org/pdf/1703.01638.pdf