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

DOI10.1145/2591796.2591869MaRDI QIDQ5259603zbMATH OpenOpenAlexFDO

Authors Sebastian Krinninger, Danupon Nanongkai, Monika R. Henzinger

Publication date 26 June 2015

Published in Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.07959

zbMATH Keywords

shortest pathsreachabilitydynamic graph algorithms

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Randomized algorithms (68W20) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Paths and cycles (05C38)

Abstract: We consider dynamic algorithms for maintaining Single-Source Reachability (SSR) and approximate Single-Source Shortest Paths (SSSP) on $n$-node $m$-edge directed graphs under edge deletions (decremental algorithms). The previous fastest algorithm for SSR and SSSP goes back three decades to Even and Shiloach [JACM 1981]; it has $O(1)$ query time and $O(mn)$ total update time (i.e., linear amortized update time if all edges are deleted). This algorithm serves as a building block for several other dynamic algorithms. The question whether its total update time can be improved is a major, long standing, open problem. In this paper, we answer this question affirmatively. We obtain a randomized algorithm with an expected total update time of $O(min(m^{7/6}{n}^{2/3+o(1)},m^{3/4}{n}^{5/4+o(1)}))=O(m{n}^{9/10+o(1)})$ for SSR and $(1+epsilon)$-approximate SSSP if the edge weights are integers from $1$ to $Wleq{2}^{lo{g}^{c}n}$ and $epsilongeq1/lo{g}^{c}n$ for some constant $c$. We also extend our algorithm to achieve roughly the same running time for Strongly Connected Components (SCC), improving the algorithm of Roditty and Zwick [FOCS 2002]. Our algorithm is most efficient for sparse and dense graphs. When $m=Theta(n)$ its running time is $O(n^{1+5/6+o(1)})$ and when $m=Theta(n^2)$ its running time is $O(n^{2+3/4+o(1)})$. For SSR we also obtain an algorithm that is faster for dense graphs and has a total update time of $O(m^{2/3}{n}^{4/3+o(1)}+m^{3/7}{n}^{12/7+o(1)})$ which is $O(n^{2+2/3})$ when $m=Theta(n^2)$. All our algorithms have constant query time in the worst case and are correct with high probability against an oblivious adversary.

Recommendations

• Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
• Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound
• A subquadratic-time algorithm for decremental single-source shortest paths
• Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
• scientific article; zbMATH DE number 7204496

Cites work

• scientific article; zbMATH DE number 5485440 (Why is no real title available?)
• scientific article; zbMATH DE number 5485574 (Why is no real title available?)
• Advances in Cryptology – CRYPTO 2004
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Bounds on the sample complexity for private learning and private data release
• Characterizing the sample complexity of private learners
• Collusion-secure fingerprinting for digital data
• Differential privacy and the fat-shattering dimension of linear queries
• Efficient algorithms for privately releasing marginals via convex relaxations
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• Interactive privacy via the median mechanism
• Iterative Constructions and Private Data Release
• Lower bounds in differential privacy
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• On the complexity of differentially private data release, efficient algorithms and hardness results
• On the geometry of differential privacy
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Theory of Cryptography

Cited in

(25)

• Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
• A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
• Decremental strongly-connected components and single-source reachability in near-linear time
• Maintaining shortest paths under deletions in weighted directed graphs
• Deterministic partially dynamic single source shortest paths for sparse graphs
• Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
• Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Decremental single-source reachability in planar digraphs
• Dynamic graph coloring
• Density independent algorithms for sparsifying \(k\)-step random walks
• Dynamic single-source shortest paths in Erdős-Rényi random graphs
• Decremental strongly connected components and single-source reachability in near-linear time
• Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
• scientific article; zbMATH DE number 7561506 (Why is no real title available?)
• Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
• Incremental single-source shortest paths in digraphs with arbitrary positive arc weights
• Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
• Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
• Randomization for efficient dynamic graph algorithms (invited talk)
• On efficient distributed construction of near optimal routing schemes
• A subquadratic-time algorithm for decremental single-source shortest paths
• Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound

Describes a project that uses

Uses Software

• SuLQ

This page was built for publication: Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259603)