On the Computational Complexity of Dynamic Graph Problsm
G. Ramalingam and Thomas Reps
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 often 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. This 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.
(Click here to access the paper:
PostScript,
PDF.)
University of Wisconsin