Dynamic graph algorithms are data structures that maintain properties of
graphs while they are modified by edge deletions and insertions. These
data structures can be used, for example, to efficiently detect deadlocks
in operating systems, compute shortest-paths in navigation systems,
or to speed up static algorithms, such as algorithms used in computer-aided
verification or certain multi-commodity flow algorithms, that solve multiple
graph propblems on very similar graphs.
While basic properties, such as connectivity, in undirected graphs can be
maintained in time polylogarithmic in the size of the graph per edge update,
no such bounds are known for basic properties, such as reachability, in
directed graphs or more sophisticated graph properties, such as shortest paths,
in undirected graphs. We will present the state of the art for these problems,
giving both upper and (conditional) lower bounds. Conditional lower bounds
result from a relatively new research direction, where similar to hardness
reductions in complexity theory, we show that based on the assumption that some
well-known problems, such as Boolean matrix multiplication, cannot be solved fast,
certain dynamic problems cannot be solved in polylogarithmic time per operation.