New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners

Understand

Maintaining and updating shortest paths information in a graph is a fundamental problem with many applications.

• As computations on dense graphs can be prohibitively expensive, and it is preferable to perform the computations on a sparse skeleton of the given graph that roughly preserves the shortest paths information.
• Spanners and emulators serve this purpose.
• This paper develops fast dynamic algorithms for sparse spanner and emulator maintenance and provides evidence from fine-grained complexity that these algorithms are tight.