Abstract
Many dynamic graph algorithms have an amortized update time, rather than a
stronger worst-case guarantee. But amortized data structures are not suitable
for real-time systems, where each individual operation has to be executed
quickly. For this reason, there exist many recent randomized results that aim
to provide a guarantee stronger than amortized expected. The strongest possible
guarantee for a randomized algorithm is that it is always correct (Las Vegas),
and has high-probability worst-case update time, which gives a bound on the
time for each individual operation that holds with high probability.
In this paper we present the first polylogarithmic high-probability
worst-case time bounds for the dynamic spanner and the dynamic maximal matching
problem. 1. For dynamic spanner, the only known $o(n)$ worst-case bounds were
$O(n^{3/4})$ high-probability worst-case update time for maintaining a
3-spanner and $O(n^{5/9})$ for maintaining a 5-spanner. We give a $O(1)^k
\log^3(n)$ high-probability worst-case time bound for maintaining a
$(2k-1)$-spanner, which yields the first worst-case polylog update time for all
constant $k$. (All the results above maintain the optimal tradeoff of stretch
$2k-1$ and $\tilde{O}(n^{1+1/k})$ edges.) 2. For dynamic maximal matching, or
dynamic $2$-approximate maximum matching, no algorithm with $o(n)$ worst-case
time bound was known and we present an algorithm with $O(\log^5(n))$
high-probability worst-case time; similar worst-case bounds existed only for
maintaining a matching that was $(2+\epsilon)$-approximate, and hence not
maximal.
Our results are achieved using a new black-box reduction that converts any
data structure with worst-case expected update time into one with a
high-probability worst-case update time: the query time remains the same, while
the update time increases by a factor of $O(\log^2(n))$.