On the computational complexity of dynamic graph problems

Abstract

A common way to evaluate the time complexity of an algorithm is to use asymptotic worst-case analysis and to express the cost of the computation as a function of the size of the input. However, for an incremental algorithm this kind of analysis is sometimes not very informative. (By an "incremental algorithm", we mean an algorithm for a dynamic problem.) When the cost of the computation is expressed as a function of the size of the (current) input, several incremental algorithms that have been proposed run in time asymptotically no better, in the worst-case, than the time required to perform the computation from scratch. Unfortunately, this kind of information is not very helpful if one wishes to compare different incremental algorithms for a given problem. This paper explores a different way to analyze incremental algorithms. Rather than express the cost of an incremental computation as a function of the size of the current input, we measure the cost in terms of the sum of the sizes of the changes in the input and the output. The change in approach allows us to develop a more informative theory of computational complexity for dynamic problems. An incremental algorithm is said to be bounded if the time taken by the algorithm to perform an update can be bounded by some function of the sum of the sizes of the changes in the input and the output. A dynamic problem is said to be unbounded with respect to a model of computation if it has no bounded incremental algorithm within that model of computation. The paper presents new upper-bound results as well as new lower-bound results with respect to a class of algorithms called the locally persistent algorithms. Our results, together with some previously known ones, shed light on the organization of the complexity hierarchy that exists when dynamic problems are classified according to their incremental complexity with respect to locally persistent algorithms. In particular, these results separate the classes of polynomially bounded problems, inherently exponentially bounded problems, and unbounded problems.