Dynamic Graphs:Introduction and Techniques for Undirected Graphs

Introduction

In many applications of graph algorithms, including communication networks, VLSI design, graphics, and assembly planning, graphs are subject to discrete changes, such as insertions or deletions of vertices or edges. In the last two decades there has been a growing interest in such dynamically changing graphs, and a whole body of algorithmic techniques and data structures for dynamic graphs has been discovered. This chapter is intended as an overview of this field.

An update on a graph is an operation that inserts or deletes edges or vertices of the graph or changes attributes associated with edges or vertices, such as cost or color. Throughout this chapter by dynamic graph we denote a graph that is subject to a sequence of updates. In a typical dynamic graph problem one would like to answer queries on dynamic graphs, such as, for instance, whether the graph is connected or which is the shortest path between any two vertices. The goal of a dynamic graph algorithm is to update efficiently the solution of a problem after dynamic changes, rather than having to recompute it from scratch each time. Given their powerful versatility, it is not surprising that dynamic algorithms and dynamic data structures are often more difficult to design and to analyze than their static counterparts.

We can classify dynamic graph problems according to the types of updates allowed. In particular, a dynamic graph problem is said to be fully dynamic if the update operations include unrestricted insertions and deletions of edges or vertices. A dynamic graph problem is said to be partially dynamic if only one type of update, either insertions or deletions, is allowed. More specifically, a dynamic graph problem is said to be incremental if only insertions are allowed, while it is said to be decremental if only deletions are allowed.

In the first part of this chapter we will present the main algorithmic techniques used to solve dynamic problems on both undirected and directed graphs. In the second part of the chapter we will deal with dynamic problems on graphs, and we will investigate as paradigmatic problems the dynamic maintenance of minimum spanning trees, connectivity, transitive closure and shortest paths. Interestingly enough, dynamic problems on directed graphs seem much harder to solve than their counterparts on undirected graphs, and require completely different techniques and tools.

Techniques for Undirected Graphs

Many of the algorithms proposed in the literature use the same general techniques, and hence we begin by describing these techniques. In this section we focus on undirected graphs, while techniques for directed graphs will be discussed in Section 36.3. Typically, most of these techniques use some sort of graph decomposition, and partition either the vertices or the edges of the graph to be maintained. Moreover, data structures that maintain properties of dynamically changing trees, such as the ones described in Chapter 35 (linking and cutting trees, topology trees, and Euler tour trees), are often used as building blocks by many dynamic graph algorithms.

Clustering

The clustering technique has been introduced by Frederickson [13] and is based upon partitioning the graph into a suitable collection of connected subgraphs, called clusters, such that each update involves only a small number of such clusters. Typically, the decomposition defined by the clusters is applied recursively and the information about the subgraphs is combined with the topology trees described in Section 35.3. A refinement of the clustering technique appears in the idea of ambivalent data structures [14], in which edges can belong to multiple groups, only one of which is actually selected depending on the topology of the given spanning tree.

As an example, we briefly describe the application of clustering to the problem of maintaining a minimum spanning forest [13]. Let G = (V, E) be a graph with a designated spanning tree S. Clustering is used for partitioning the vertex set V into subtrees connected in S, so that each subtree is only adjacent to a few other subtrees. A topology tree, as described in Section 35.3, is then used for representing a recursive partition of the tree S. Finally, a generalization of topology trees, called 2-dimensional topology trees, are formed from pairs of nodes in the topology tree and allow it to maintain information about the edges in E S [13].

Fully dynamic algorithms based only on a single level of clustering obtain typically time bounds of the order of O(m2/3) (see for instance [17, 32]). When the partition can be applied recursively, better O(m1/2) time bounds can be achieved by using 2-dimensional topology trees (see, for instance, [13, 14]).

THEOREM 36.1 (Frederickson [13]) The minimum spanning forest of an undirected graph can be maintained in time O(m ) per update, where m is the current number of edges in the graph.

We refer the interested reader to [13, 14] for details about Frederickson’s algorithm. With the same technique, an O(m) time bound can be obtained also for fully dynamic connectivity and 2-edge connectivity [13, 14] The type of clustering used can very problem-dependent, however, and makes this technique difficult to be used as a black box.

Sparsification

Sparsification is a general technique due to Eppstein et al. [10] that can be used as a black box (without having to know the internal details) in order to design and dynamize graph algorithms. It is a divide-and-conquer technique that allows it to reduce the dependence on the number of edges in a graph, so that the time bounds for maintaining some property of the graph match the times for computing in sparse graphs. More precisely, when the technique is applicable, it speeds up a T (n, m) time bound for a graph with n vertices and m edges to T (n, O(n)), i.e., to the time needed if the graph were sparse. For instance, if T (n, m) = O(m ), we get a better bound of O(n ). The technique itself is quite simple.

A key concept is the notion of certificate.

DEFINITION 36.1 For any graph property P and graph G, a certificate for G is a graph Gl such that G has property P if and only if Gl has the property.

Let G be a graph with m edges and n vertices. We partition the edges of G into a collection of O(m/n) sparse subgraphs, i.e., subgraphs with n vertices and O(n) edges. The information relevant for each subgraph can be summarized in a sparse certificate. Certificates are then merged in pairs, producing larger subgraphs which are made sparse by again computing their certificate. The result is a balanced binary tree in which each node is represented by a sparse certificate. Each update involves O(log(m/n))graphs with O(n) edges each, instead of one graph with m edges.

There exist two variants of sparsification. The first variant is used in situations where no previous fully dynamic algorithm is known. A static algorithm is used for recomputing a sparse certificate in each tree node affected by an edge update. If the certificates can be found in time O(m + n), this variant gives time bounds of O(n) per update.

In the second variant, certificates are maintained using a dynamic data structure. For this to work, a stability property of certificates is needed, to ensure that a small change in the input graph does not lead to a large change in the certificates. We refer the interested reader to [10] for a precise definition of stability. the form O(mp) into O(np).

This variant transforms time bounds of DEFINITION 36.2 A time bound T (n) is well-behaved if, for some c < 1, T (n/2) < cT (n). Well-behavedness eliminates strange situations in which a time bound fluctuates wildly with n. For instance, all polynomials are well-behaved.

THEOREM 36.2 (Eppstein et al. [10]) Let P be a property for which we can find sparse certificates in time f (n, m) for some well-behaved f , and such that we can construct a data structure for testing property P in time g(n, m) which can answer queries in time q(n, m). Then there is a fully dynamic data structure for testing whether a graph has property P , for which edge insertions and deletions can be performed in time O(f (n, O(n))) + g(n, O(n)), and for which the query time is q(n, O(n)).

THEOREM 36.3 (Eppstein et al. [10]) Let P be a property for which stable sparse certificates can be maintained in time f (n, m) per update, where f is well-behaved, and for which there is a data structure for property P with update time g(n, m) and query time q(n, m). Then P can be maintained in time O(f (n, O(n))) + g(n, O(n)) per update, with query time q(n, O(n)).

Basically, the first version of sparsification (Theorem 36.2) can be used to dynamize static algorithms, in which case we only need to compute efficiently sparse certificates, while the second version (Theorem 36.3) can be used to speed up existing fully dynamic algorithms, in which case we need to maintain efficiently stable sparse certificates.

Sparsification applies to a wide variety of dynamic graph problems, including minimum spanning forests, edge and vertex connectivity. As an example, for the fully dynamic minimum spanning tree problem, it reduces the update time from O(m ) [13, 14] to O(n ) [10].

Since sparsification works on top of a given algorithm, we need not to know the internal details of this algorithm. Consequently, it can be applied orthogonally to other data structuring techniques: in a large number of situations both clustering and sparsification have been combined to produce an efficient dynamic graph algorithm.

Randomization

Clustering and sparsification allow one to design efficient deterministic algorithms for fully dynamic problems. The last technique we present in this section is due to Henzinger and King [20], and allows one to achieve faster update times for some problems by exploiting the power of randomization.

We now sketch how the randomization technique works taking the fully dynamic connectivity problem as an example. Let G = (V, E) be a graph to be maintained dynamically, and let F be a spanning forest of G. We call edges in F tree edges, and edges in E F non-tree edges. The algorithm by Henzinger and King is based on the following ingredients.

Maintaining Spanning Forests

Trees are maintained using the Euler Tours data structure (ET trees) described in Section 35.5: this allows one to obtain logarithmic updates and queries within the forest.

Random Sampling

Another key idea is the following: when e is deleted from a tree T , use random sampling among the non-tree edges incident to T , in order to find quickly a replacement edge for e, if any.

Graph Decomposition

The last key idea is to combine randomization with a suitable graph decomposition. We maintain an edge decomposition of the current graph G using O(log n) edge disjoint sub- graphs Gi = (V, Ei). These subgraphs are hierarchically ordered. The lower levels contain tightly-connected portions of G (i.e., dense edge cuts), while the higher levels contain loosely-connected portions of G (i.e., sparse cuts). For each level i, a spanning forest for the graph defined by all the edges in levels i or below is also maintained.

Note that the hard operation in this problem is the deletion of a tree edge: indeed, a spanning forest is easily maintained with the help of the linking and cutting trees described in Section 35.2 throughout edge insertions, and deleting a non-tree edge does not change the forest.

The goal is an update time of O(log3 n): after an edge deletion, in the quest for a replacement edge, we can afford a number of sampled edges of O(log2 n). However, if the candidate set of edge e is a small fraction of all non-tree edges which are adjacent to T , it is unlikely to find a replacement edge for e among this small sample. If we found no candidate among the sampled edges, we must check explicitly all the non-tree edges adjacent to T .

After random sampling has failed to produce a replacement edge, we need to perform this check explicitly, otherwise we would not be guaranteed to provide correct answers to the queries. Since there might be a lot of edges which are adjacent to T , this explicit check could be an expensive operation, so it should be made a low probability event for the randomized algorithm. This can produce pathological updates, however, since deleting all edges in a relatively small candidate set, reinserting them, deleting them again, and so on will almost surely produce many of those unfortunate events.

The graph decomposition is used to prevent the undesirable behavior described above. If a spanning forest edge e is deleted from a tree at some level i, random sampling is used to quickly find a replacement for e at that level. If random sampling succeeds, the tree is reconnected at level i. If random sampling fails, the edges that can replace e in level i form with high probability a sparse cut. These edges are moved to level i +1 and the same procedure is applied recursively on level i + 1.

THEOREM 36.4 (Henzinger and King [20]) Let G be a graph with m0 edges and n vertices subject to edge deletions only. A spanning forest of G can be maintained in O(log3 n) expected amortized time per deletion, if there are at least Ω(m0) deletions. The time per query is O(log n).

Related posts:

Leave a comment

Your email address will not be published. Required fields are marked *