Decremental Shortest Paths and Beyond

This lecture focuses on a fundamental problem in dealing with graphs that evolve over time called decremental single-source shortest paths.
This problem concerns maintaining the distances and shortest paths between a given source node and every other node in a graph undergoing edge deletions.

In this talk, I will discuss the recent development on this problem which leads to a randomized (1+ε)-approximation algorithm with near-linear total update time on undirected graphs. I will also discuss the main technique called hop-set which has found many new applications beyond the decremental shortest paths problem.

The talk will also touch some lower bound developments and other variations of the problem.