Furthermore, our algorithms offer a self-check capability.
At the end, after all updates and queries have been processed online, each algorithm can deterministically check if it might have made a mistake.
If the self-check passes, it is guaranteed that no incorrect answer was given. Otherwise, the algorithm may have made a mistake.
However, as we show in the following, the self-check passes with high probability.
This feature
implies that we can obtain Las Vegas algorithms for certain non-dynamic problems whose solutions employ decremental (2-edge-)connectivity algorithms as subroutines: we
simply repeat trying to solve the static problem from scratch, each time with new random bits, until the final self-check is passed.
With high probability, we are done already
after the first round. A nice concrete example is the algorithm of
Gabow, Kaplan, and Tarjan [1]} for the static problem of deciding if a
graph has a unique perfect matching. The algorithm
uses a decremental 2-edge-connectivity
algorithm as a subroutine. With our
decremental 2-edge-connectivity algorithm,
repeating until the self-check is passed,
we obtain a Las Vegas
algorithm for the unique perfect matching problem that is always correct, and which terminates in \(O(m + n\operatorname{polylog}n)\)  time with high probability.
