Under the traditional procedural viewpoint, an algorithm is a set of instructions that transforms a given input into the desired output. While this paradigm has been successfully applied in theory and practice to develop algorithms that have entered our everyday lives, it completely neglects the fact that in many scenarios the input is not given in its entirety at the beginning of the algorithm. Instead it often seems natural to consider a more "reactive" viewpoint in which the input is constantly undergoing changes and the algorithm needs to adapt its output after each change to the input. This has motivated theoretical computer scientists to consider "dynamic algorithms" that can deal with such changes to the input in an explicit manner. In particular for graph algorithms, one of the domains of algorithm design with a very rich history, researchers have studied dynamic versions with increasing interest in the past years.
However, a very important question has not been addressed systematically yet: Can the state-of-the-art dynamic algorithms be extended to stronger adversarial models for creating the sequence of changes to the graph? This question has two main aspects: (1) Many dynamic algorithms are randomized and assume that the sequence of changes is independent of the random choices made by the algorithm. This assumption is obstructive in many situations where the next change to the graph naturally depends on the previous outputs of the algorithm. (2) Many dynamic algorithms achieve amortized running time guarantees, which means that the stated guarantee on processing each change only holds on average and occasionally significantly more time might be needed. This is insufficient for real-time systems where hard worst-case update-time guarantees are necessary, i.e., where the adversary needs to be served after a fixed waiting time and cannot be stalled. The goal of this project is to design dynamic algorithms free from these shortcomings.