Reduction from Replacement Paths Problem (RPP) to 1-sensitive decremental st-shortest paths

FROM: Replacement Paths Problem (RPP) TO: 1-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 directed 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