ON THE COMPUTATIONAL-COMPLEXITY OF DYNAMIC GRAPH PROBLEMS

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 computa tion as a function of the size of the input. However, for an increment al algorithm this kind of analysis is sometimes not very informative. (By an ''incremental algorithm'', we mean an algorithm for a dynamic p roblem.) When the cost of the computation is expressed as a function o f 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 wi shes 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 funct ion 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 c hange in approach allows us to develop a more informative theory of co mputational 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 pres ents new upper-bound results as well as new lower-bound results with r espect to a class of algorithms called the locally persistent algorith ms. Our results, together with some previously known ones, shed light on the organization of the complexity hierarchy that exists when dynam ic problems are classified according to their incremental complexity w ith respect to locally persistent algorithms. In particular, these res ults separate the classes of polynomially bounded problems, inherently exponentially bounded problems, and unbounded problems.