ALCOMFT-TR-01-147

C. Demetrescu
Fully Dynamic Algorithms for Path Problems on Directed Graphs
Rome. Work packages 2, 4 and 5. June 2001.

Abstract: In this thesis we investigate fully dynamic algorithms for path problems on directed graphs. In particular, we focus on two of the most fundamental path problems: fully dynamic transitive closure and fully dynamic single-source shortest paths. The first part of the thesis presents a new technique which makes it possible to reduce fully dynamic transitive closure to the problem of reevaluating polynomials over matrices when updates of variables are performed. Based on this technique, we devise a new deterministic algorithm which improves the best known bounds for fully dynamic transitive closure. Our algorithm hinges upon the well-known equivalence between transitive closure and matrix multiplication on a closed semiring. We show how to maintain explicitly the transitive closure of a directed graph as a Boolean matrix in O(n²) amortized time per insertion and deletion of edges. Since an update may change as many as Omega(n²) entries of this matrix, this seems to be the best update bound that one could hope for this class of algorithms. We note that maintaining explicitly the transitive closure allows us to answer reachability queries with just one table lookup. We also consider the case where only deletions are allowed and we show how to handle updates faster in O(n) amortized time per operation while maintaining unit lookup per query; in this way we generalize to directed graphs the previous best known deletions-only result for acyclic graphs. Using the same matrix based approach, we also address the problem of maintaining implicitly the transitive closure of a directed graph and we devise the first algorithm which supports both updates and reachability queries in subquadratic time per operation. This result proves that it is actually possible to break through the O(n²) barrier on the single-operation complexity of fully dynamic transitive closure, and solves a problem that has been open for many years. Our subquadratic algorithm is randomized Monte Carlo and supports update in O(n^1.58) and query in O(n^0.58) worst-case time. From an experimental point of view, we investigate the practical performances of fully dynamic single-source shortest paths algorithms on directed graphs with arbitrary edge weights. We also propose a variant of the best known algorithms especially designed to be simple and fast in practice while matching the same asymptotic worst-case running time. Our study provides the first experimental evidence of practical dynamic solutions for the problem that are better by several orders of magnitude than recomputing from scratch.

Postscript file: ALCOMFT-TR-01-147.ps.gz (455 kb).