Sparsification — A technique for speeding up dynamic graph algorithms

David Eppstein,
Zvi Galil,
Giuseppe F. Italiano,
and Amnon Nissenzweig

*J. ACM* 44(5):669–696, Sep 1997

*Mathematical Reviews* 98k:68039, 1998

Reviewed by Peter B. Gibbons

This paper makes a major contribution to the study of dynamic graph algorithms that maintain some property of a changing graph more efficiently than recomputation from scratch after each change. Dynamic algorithms can be classified as fully dynamic, where both edge insertions and deletions are allowed, or as partially dynamic where only insertions are allowed. The improved performances for dynamic algorithms are achieved through the use of the new technique of sparsification which, when applicable, can speed up a $T(n,m)$ time bound for a graph $G$ with $n$ vertices and $m$ edges to $T(n,O(n))$, almost the time needed if $G$ were sparse. Sparsification involves partitioning the edges of $G$ into a collection of $O(m/n)$ sparse subgraphs, each with $n$ vertices and $O(n)$ edges. The information relevant for each subgraph can be summarised in an even sparser subgraph, called a sparse certificate. Certificates are merged in pairs, producing larger subgraphs which are made sparse again by computing their certificates. The result is a balanced binary tree in which each node is represented by a sparse certificate. Each update involves $\log (m/n)$ graphs with $O(n)$ edges each, instead of one graph with $m$ edges. A more careful partition into subgraphs causes each update to involve a sequence of graphs with $O(n)$ edges in total. Three variants of the sparsification technique are developed. The first is used in situations where no previous fully dynamic algorithm was known and gives time bounds of $O(n)$ per update. The second variant uses a dynamic data structure to maintain certificates possessing a stability property, thereby transforming time bounds of the form $O(m\sp p)$ into $O(n\sp p)$. In the third variant, deletions are performed as in the first variant, and insertions by using a partially dynamic algorithm. This leads to insertion times often matching those of known partially dynamic algorithms, together with deletion times similar to those of the first variant. Results include the maintenance of minimum spanning forests, graph connectivity, graph 2-edge connectivity and bipartiteness in time $O(n\sp {1/2})$ per change; 3-edge connectivity in time $O(n\sp {2/3})$ per change; 4-edge connectivity in time $O(n\alpha(n))$ per change; $k$-edge connectivity for constant $k$ in time $O(n\log n)$ per change; 2-vertex connectivity and 3-vertex connectivity in time $O(n)$ per change; and 4-vertex connectivity in time $O(n\alpha(n))$ per change. Further results speed up the insertion times to match the bounds of known partially dynamic algorithms. The paper concludes with sections on recent related work and remaining open questions.