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

DOI10.1145/2591796.2591869zbMATH Open1315.68280arXiv1504.07959OpenAlexW3098654413MaRDI QIDQ5259603FDOQ5259603

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)

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.

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

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

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)

Cites Work

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

Cited In (19)

• Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
• Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
• Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
• Dynamic Single-Source Shortest Paths in Erdös-Rényi Random Graphs
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Density Independent Algorithms for Sparsifying k-Step Random Walks
• Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time
• Title not available (Why is that?)
• Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
• Dynamic graph coloring
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• On efficient distributed construction of near optimal routing schemes
• Title not available (Why is that?)
• Maintaining shortest paths under deletions in weighted directed graphs
• Randomization for Efficient Dynamic Graph Algorithms
• Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
• Incremental single-source shortest paths in digraphs with arbitrary positive arc weights

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)