# Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time

@article{Brand2019DynamicAS, title={Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time}, author={Jan van den Brand and Danupon Nanongkai}, journal={2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)}, year={2019}, pages={436-455} }

Consider the following distance query for an n-node graph G undergoing edge insertions and deletions: given two sets of nodes I and J, return the distances between every pair of nodes in I × J. %It generalizes several versions of the dynamic shortest paths problem such as Single-Source and All-Pairs Shortest Paths (SSSP and APSP). This query is rather general and captures several versions of the dynamic shortest paths problem. In this paper, we develop an efficient (1 + ε) -approximation… Expand

#### Figures and Topics from this paper

#### 17 Citations

Fast Deterministic Fully Dynamic Distance Approximation

- Computer Science
- ArXiv
- 2021

Improved dynamic algorithms that, given an unweighted and undirected graph G = (V,E) undergoing edge insertions and deletions, and a parameter 0 < ≤ 1, maintain (1 + )-approximations of the st distance of a single pair of nodes, the distances from a single source to all nodes, or the distances between all nodes are obtained. Expand

Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier

- Computer Science
- ArXiv
- 2021

Given a directed, weighted graph G = (V,E) undergoing edge insertions, the incremental single-source shortest paths (SSSP) problem asks for the maintenance of approximate distances from a dedicated… Expand

Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds

- Computer Science, Mathematics
- SODA
- 2020

These are the first exact dynamic algorithms with truly-subcubic update time \emph{and} space usage and match the worst-case update time of the best previous algorithms and the second algorithm improves upon a Monte-Carlo algorithm in a weaker adversary model with the same running time. Expand

Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs

- Computer Science
- ESA
- 2020

This paper gives a fully dynamic single-source shortest paths data structure for planar weighted digraphs with worst-case update time and O(log2 n) query time, and obtains a data structure maintaining a planar digraph under edge insertions and deletions capable of returning the identifier of the strongly connected component of any query vertex. Expand

Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs

- Mathematics, Computer Science
- ArXiv
- 2020

This thesis presents new techniques to deal with fundamental algorithmic graph problems where graphs are directed and partially dynamic, i.e. undergo either a sequence of edge insertions or deletions, and obtains the first randomized data structure to maintain SSR and SCCs in near-optimal total update time in a graph undergoing edge deletions. Expand

Constructing a Distance Sensitivity Oracle in O(n2.5794M) Time

- Computer Science
- ICALP
- 2021

The main technical ingredient is an algorithm that computes the inverse of a degree-d polynomial matrix modulo x, which improves the O(n2.6865M) time bound in [Ren, ESA 2020], and matches the current best time bound for computing all-pairs shortest paths. Expand

Sensitive Distance and Reachability Oracles for Large Batch Updates

- Computer Science, Mathematics
- 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
- 2019

The first sensitive reachability oracle can handle f≥log n updates is obtained and is the first graph algorithm that exploits the kernel basis decomposition of polynomial matrices by the symbolic computation community. Expand

Tight conditional lower bounds for approximating diameter in directed graphs

- Computer Science, Mathematics
- STOC
- 2021

This work proves that under SETH for any δ>0, a (2k−1/k−δ)-approximation algorithm for Diameter on directed unweighted graphs requires mk/k+1−o(1) time, and obtains a series of conditional lower bounds that give a complete time-accuracy trade-off that is tight with the three known algorithms for directed graphs. Expand

Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds

- Computer Science, Mathematics
- 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
- 2019

Improved algorithms for dynamic matrix inverse and their extensions to some incremental/look-ahead variants, and variants of the Online Matrix-Vector conjecture that, if true, imply that these algorithms are tight are presented. Expand

Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler

- Computer Science, Mathematics
- SODA
- 2020

This article develops several new techniques including improved decremental cover data structures for graphs, a more efficient notion of the heavy/light decomposition framework introduced by Chechik and Bernstein and the first clustering technique to maintain a dynamic \emph{sparse} emulator in the deterministic setting. Expand

#### References

SHOWING 1-10 OF 72 REFERENCES

Fully dynamic all-pairs shortest paths with worst-case update-time revisited

- Computer Science, Mathematics
- SODA
- 2017

This work revisits the classic problem of dynamically maintaining shortest paths between all pairs of nodes of a directed weighted graph and gives worst-case guarantees on the time needed to process a single update, and shows that randomization along with a more direct approach can provide better bounds. Expand

Deterministic decremental single source shortest paths: beyond the o(mn) bound

- Mathematics, Computer Science
- STOC
- 2016

This paper presents the first deterministic decremental SSSP algorithm that breaks the Even-Shiloach bound of O(mn) total update time, for unweighted and undirected graphs, and is faster than all existing randomized algorithms. Expand

A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths

- Computer Science, Mathematics
- SODA
- 2014

The first approximation algorithm whose total update time is faster than O(mn) for all values of m is obtained, and is the first that breaks through the quadratic time barrier. Expand

On Dynamic Shortest Paths Problems

- Mathematics, Computer Science
- Algorithmica
- 2010

Reductions that show that the incremental and decremental single-source shortest-paths problems, for weighted directed or undirected graphs, are, in a strong sense, at least as hard as the static all-pairs shortest- Paths problem. Expand

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization

- Mathematics, Computer Science
- 2013 IEEE 54th Annual Symposium on Foundations of Computer Science
- 2013

An algorithm with a total update time of Ȏ(n5/2) and constant query time that has an additive error of two in addition to the 1 + ϵ multiplicative error is presented, giving the first improved deterministic algorithm since 1981. Expand

Dynamic approximate all-pairs shortest paths in undirected graphs

- Mathematics, Computer Science
- 45th Annual IEEE Symposium on Foundations of Computer Science
- 2004

Three dynamic algorithms for the approximate all-pairs shortest paths problem in unweighted undirected graphs, including a fully dynamic algorithm with an expected amortized update time of O(mn/t) and worst-case query time ofO(t). Expand

Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs

- Mathematics, Computer Science
- STOC
- 2014

A randomized algorithm is obtained which achieves an Õ (mn0.984) expected total update time for SSR and (1 + ε)-approximate SSSP, where Õ(·) hides poly log n and this algorithm serves as a building block for several other dynamic algorithms. Expand

Algorithms and Hardness for Diameter in Dynamic Graphs

- Computer Science, Mathematics
- ICALP
- 2019

This paper provides a comprehensive study of the dynamic approximation of Diameter, Radius and Eccentricities, providing both conditional lower bounds, and new algorithms whose bounds are optimal under popular hypotheses in fine-grained complexity. Expand

Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs

- Mathematics, Computer Science
- ICALP
- 2017

This paper presents the first deterministic algorithm for undirected, unweighted graphs to go beyond the $O(mn)$ bound, and poses as a major open problem the question of derandomizing their result. Expand

Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time

- Mathematics, Computer Science
- J. ACM
- 2018

This article gives a (1+ε)-approximation algorithm with m1+o(1) expected total update time, thus obtaining near-linear time and can maintain an (no(1), ε)-hop set ofnear-linear size in near- linear time under edge deletions. Expand