2020/09/17 by Julia Chuzhoy, Thatchaphol Saranurak, Chuzhoy, Julia +1 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #Complexity and Algorithms in Graphs #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2009.08479
In the decremental single-source shortest paths (SSSP) problem, the input is\nan undirected graph G=(V,E) with n vertices and m edges undergoing edge\ndeletions, together with a fixed source vertex s\∈ V. The goal is to\nmaintain a data structure that supports shortest-path queries: given a vertex\nv\∈ V, quickly return an (approximate) shortest path from s to v. The\ndecremental all-pairs shortest paths (APSP) problem is defined similarly, but\nnow the shortest-path queries are allowed between any pair of vertices of V.\nBoth problems have been studied extensively since the 80's, and algorithms with\nnear-optimal total update time and query time have been discovered for them.\nUnfortunately, all these algorithms are randomized and, more importantly, they\nneed to assume an oblivious adversary.\n Our first result is a deterministic algorithm for the decremental SSSP\nproblem on weighted graphs with O(n2+o(1)) total update time, that\nsupports (1+\ε)-approximate shortest-path queries, with query time\nO(|P|\⋅ no(1)), where P is the returned path. This is the first\n(1+\ε)-approximation algorithm against an adaptive adversary that\nsupports shortest-path queries in time below O(n), that breaks the O(mn)\ntotal update time bound of the classical algorithm of Even and Shiloah from\n1981.\n Our second result is a deterministic algorithm for the decremental APSP\nproblem on unweighted graphs that achieves total update time\nO(n2.5+\δ), for any constant \δ>0, supports approximate distance\nqueries in O(\log\log n) time; the algorithm achieves an\nO(1)-multiplicative and no(1)-additive approximation on the path length.\nAll previous algorithms for APSP either assume an oblivious adversary or have\nan \Ω(n3) total update time when m=\Ω(n2).\n