Given a weighted undirected graph G=(V,E,w), a hopset H of hopbound \beta and stretch (1+\epsilon) is a set of edges such that for any pair of nodes u, v \in V, there is a path in G \cup H of at most \beta hops, whose length is within a (1+\epsilon) factor from the distance between u and v in G. We provide a decremental algorithm for maintaining hopsets with a polylogarithmic hopbound , with a total update time that matches the best known static algorithm up to polylogarithmic factors. Previously, the best known decremental hopset algorithm had a hopbound of 2^{\tilde{O(\log^{3/4} n)}[HKN, FOCS'14]. Our decremental hopset algorithm allows us to obtain the following improved decremental algorithms for maintaining shortest paths. -(1+\epsilon) -approximate single source shortest paths in amortized update time }  of 2^{ (\sqrt{\log n } . This improves super-polynomially over the best known amortized update time of 2^{\tilde{O(\log^{3/4} n)} by } [  HKN, FOCS'14  ]. - ( 1+\epsilon)-approximate shortest paths from a set of s sources in (s) amortized update time, assuming that s= n^{\Omega(1), and |E|= n^{1+\Omega(1)}. In this regime, we give the first decremental algorithm, whose running time matches, up to polylogarithmic factors, the best known static algorithm. -(} 2k-1)(1+\epsilon)-approximate all-pairs shortest paths (for any constant k \geq 2), in \tilde{O}(n^{1/k}) amortized update time and O(k) query time. This improves over the best-known amortized update time of%DIFDELCMD < \tilde{O}%%% (n^{1/k)\cdot(1/\epsilon)^{O(\sqrt{\log n})} }  [Chechik, FOCS'18] . Moreover, we reduce the query time from O(\log \log(nW)) to a constant O(k), and hence eliminate the dependence on nand the aspect ratio W\cdot(\frac{1}{\epsilon})^{\tilde{O}(\sqrt{\log n})}. For sparse graphs our construction nearly matches the best known static running time/ query time tradeoff} .
Given a weighted undirected graph G=(V,E,w), a hopset H of hopbound \beta and stretch (1+\epsilon) is a set of edges such that for any pair of nodes u, v \in V, there is a path in G \cup H of at most \beta hops, whose length is within a (1+\epsilon) factor from the distance between u and v in G. We show the first efficient decremental algorithm for maintaining hopsets with a polylogarithmic hopbound . The update time of our algorithm matches the best known static algorithm up to polylogarithmic factors. (\log^{3/4} n)}[HKN, FOCS'14]. Our decremental hopset algorithm allows us to obtain the following improved decremental algorithms for maintaining shortest paths. -(1+\epsilon) -approximate single source shortest paths in amortized update time } All the previous decremental hopset constructions had a superpolylogarithmic (but subpolynomial) hopbound of 2^{ \log^{\Omega(1) } (\log^{3/4} n)} by } [ Bernstein, FOCS'09; HKN, FOCS'14 ; Chechik, FOCS'18 ]. By applying our decremental hopset construction, we get improved or near optimal bounds for several distance problems. Most importantly, we show how to decrementally maintain ( , and |E|= n^{1+\Omega(1)}. In this regime, we give the first decremental algorithm, whose running time matches, up to polylogarithmic factors, the best known static algorithm. -(} 2k-1)(1+\epsilon)-approximate all-pairs shortest paths (for any constant k \geq 2), in \tilde{O}(n^{1/k}) amortized update time and O(k) query time. This %DIFDELCMD < \tilde{O}%%% )\cdot(1/\epsilon)^{O(\sqrt{\log n})} } significantly improves (by a polynomial factor) over the update-time of the best previously known decremental algorithm in the constant query time regime. Moreover, it improves over the result of [Chechik, FOCS'18] that has a query time of O(\log \log(nW)) , where W is the aspect ratio, and the amortized update time is n^{1/k\cdot(\frac{1}{\epsilon})^{\tilde{O}(\sqrt{\log n})}. For sparse graphs our construction nearly matches the best known static running time/ query time tradeoff} .
R
provide a
show the first efficient
R
, with a total update time that
. The update time of our algorithm
D
Previously, the best known decremental hopset algorithm had a hopbound of 2^{\tilde{O
A
All the previous decremental hopset constructions had a superpolylogarithmic (but subpolynomial) hopbound
R
(\sqrt{\log n
\log^{\Omega(1)
D
. This improves super-polynomially over the best known amortized update time of 2^{\tilde{O
A
Bernstein, FOCS'09;
A
; Chechik, FOCS'18
R
-
By applying our decremental hopset construction, we get improved or near optimal bounds for several distance problems. Most importantly, we show how to decrementally maintain
D
1+\epsilon)-approximate shortest paths from a set of s sources in
D
(s) amortized update time, assuming that s= n^{\Omega(1)
D
improves over the best-known amortized update time of
D
(n^{1/k
A
significantly improves (by a polynomial factor) over the update-time of the best previously known decremental algorithm in the constant query time regime. Moreover, it improves over the result of
R
. Moreover, we reduce the query time from
that has a query time of
R
to a constant O(k), and hence eliminate the dependence on nand the aspect ratio W
, where W is the aspect ratio, and the amortized update time is n^{1/k