Dynamic Graphs:Techniques for Directed Graphs

Techniques for Directed Graphs

In this section we discuss the main techniques used to solve dynamic path problems on directed graphs. We first address combinatorial and algebraic properties, and then we con- sider some efficient data structures, which are used as building blocks in designing dynamic algorithms for transitive closure and shortest paths. Similarly to the case of undirected graphs seen in Section 36.2, data structures that maintain properties of dynamically changing trees, such as the ones described in Chapter 35 (reachability trees), are often used as building blocks by many dynamic graph algorithms.

Kleene Closures

Path problems such as transitive closure and shortest paths are tightly related to matrix sum and matrix multiplication over a closed semiring (see [5] for more details). In particular, the transitive closure of a directed graph can be obtained from the adjacency matrix of the graph via operations on the semiring of Boolean matrices, that we denote by {+, ·, 0, 1}. In this case, + and · denote the usual sum and multiplication over Boolean matrices.

LEMMA 36.1 Let G = (V, E) be a directed graph and let TC(G) be the (reflexive) transitive closure of G. If X is the Boolean adjacency matrix of G, then the Boolean

adjacency matrix of TC(G) is the Kleene closure of X on the {+, ·, 0, 1} Boolean semiring:

Similarly, shortest path distances in a directed graph with real-valued edge weights can be obtained from the weight matrix of the graph via operations on the semiring of real-valued matrices, that we denote by {⊕, 8, R}, or more simply by {min, +}. Here, R is the set of real values and ⊕ and 8 are defined as follows. Given two real-valued matrices A and B, C = A 8 B is the matrix product such that C[x, y] = min1≤z≤n{A[x, z] + B[z, y]} and D = A ⊕ B is the matrix sum such that D[x, y] = min{A[x, y], B[x, y]}. We also denote by AB the product A 8 B and by AB[x, y] entry (x, y) of matrix AB.

LEMMA 36.2 Let G = (V, E) be a weighted directed graph with no negative-length cycles. If X is a weight matrix such that X[x, y] is the weight of edge (x, y) in G, then the distance matrix of G is the Kleene closure of X on the {⊕, 8, R} semiring:

We now briefly recall two well-known methods for computing the Kleene closure X∗ of X. In the following, we assume that X is an n × n matrix.

Logarithmic Decomposition

A simple method to compute X∗, based on repeated squaring, requires O(nµ · log n) worst- case time, where O(nµ ) is the time required for computing the product of two matrices over a closed semiring. This method performs log2 n sums and products of the form Xi+1 = Xi + X2, where X = X0 and X ∗ = Xlog n.

Recursive Decomposition

Another method, due to Munro [28], is based on a Divide and Conquer strategy and computes X ∗ in O(nµ) worst-case time. Munro observed that, if we partition X in four sub- matrices A, B, D, C of size n/2 × n/2 (considered in clockwise order), and X ∗ similarly in four submatrices E, F , H, G of size n/2 × n/2, then X ∗ is defined recursively according to the following equations:

Surprisingly, using this decomposition the cost of computing X∗ starting from X is asymptotically the same as the cost of multiplying two matrices over a closed semiring.

Long Paths

In this section we recall an intuitive combinatorial property of long paths in a graph. Namely, if we pick a subset S of vertices at random from a graph G, then a sufficiently long path will intersect S with high probability. This can be very useful in finding a long path by using short searches.

To the best of our knowledge, the long paths property was first given in [18], and later on it has been used many times in designing efficient algorithms for transitive closure and shortest paths (see e.g., [7, 24, 37, 38]). The following theorem is from [37].

THEOREM 36.5 (Ullman and Yannakakis [37]) Let S ⊆ V be a set of vertices chosen uniformly at random. Then the probability that a given simple path has a sequence of more than (cn log n)/|S| vertices, none of which are from S, for any c > 0, is, for sufficiently large n, bounded by 2−αc for some positive α.

Zwick [38] showed it is possible to choose set S deterministically by a reduction to a hitting set problem [3, 27]. King used a similar idea for maintaining fully dynamic shortest paths [24].

Locality

Recently, Demetrescu and Italiano [8] proposed a new approach to dynamic path problems based on maintaining classes of paths characterized by local properties, i.e., properties that hold for all proper subpaths, even if they may not hold for the entire paths. They showed that this approach can play a crucial role in the dynamic maintenance of shortest paths. For instance, they considered a class of paths defined as follows:

DEFINITION 36.3 A path π in a graph is locally shortest if and only if every proper subpath of π is a shortest path.

This definition is inspired by the optimal-substructure property of shortest paths: all subpaths of a shortest path are shortest. However, a locally shortest path may not be shortest.

The fact that locally shortest paths include shortest paths as a special case makes them an useful tool for computing and maintaining distances in a graph. Indeed, paths defined locally have interesting combinatorial properties in dynamically changing graphs. For example, it is not difficult to prove that the number of locally shortest paths that may change due to an edge weight update is O(n2) if updates are partially dynamic, i.e., increase-only or decrease-only:

THEOREM 36.6 Let G be a graph subject to a sequence of increase-only or decrease-only edge weight updates. Then the amortized number of paths that start or stop being locally shortest at each update is O(n2).

Unfortunately, Theorem 36.6 does not hold if updates are fully dynamic, i.e., increases and decreases of edge weights are intermixed. To cope with pathological sequences, a possible solution is to retain information about the history of a dynamic graph, considering the following class of paths:

DEFINITION 36.4 A historical shortest path (in short, historical path) is a path that has been shortest at least once since it was last updated.

Here, we assume that a path is updated when the weight of one of its edges is changed. Applying the locality technique to historical paths, we derive locally historical paths:

DEFINITION 36.5 A path π in a graph is locally historical if and only if every proper subpath of π is historical.

Like locally shortest paths, also locally historical paths include shortest paths, and this makes them another useful tool for maintaining distances in a graph:

LEMMA 36.3 If we denote by SP , LSP , and LHP respectively the sets of shortest paths, locally shortest paths, and locally historical paths in a graph, then at any time the following inclusions hold: SP ⊆ LSP ⊆ LHP .

Differently from locally shortest paths, locally historical paths exhibit interesting combinatorial properties in graphs subject to fully dynamic updates. In particular, it is possible to prove that the number of paths that become locally historical in a graph at each edge weight update depends on the number of historical paths in the graph.

THEOREM 36.7 (Demetrescu and Italiano [8]) Let G be a graph subject to a sequence of update operations. If at any time throughout the sequence of updates there are at most O(h) historical paths in the graph, then the amortized number of paths that become locally historical at each update is O(h).

To keep changes in locally historical paths small, it is then desirable to have as few historical paths as possible. Indeed, it is possible to transform every update sequence into a slightly longer equivalent sequence that generates only a few historical paths. In particular, there exists a simple smoothing strategy that, given any update sequence Σ of length k, produces an operationally equivalent sequence F (Σ) of length O(k log k) that yields only O(log k) historical shortest paths between each pair of vertices in the graph. We refer the interested reader to [8] for a detailed description of this smoothing strategy. According to Theorem 36.7, this technique implies that only O(n2 log k) locally historical paths change at each edge weight update in the smoothed sequence F (Σ).

As elaborated in [8], locally historical paths can be maintained very efficiently. Since by Lemma 36.3 locally historical paths include shortest paths, this yields the fastest known algorithm for fully dynamic all pairs shortest paths (see Section 36.7.2).

Matrices

Another useful data structure for keeping information about paths in dynamic directed graphs is based on matrices subject to dynamic changes. As we have seen in Section 36.3.1, Kleene closures can be constructed by evaluating polynomials over matrices. It is there- fore natural to consider data structures for maintaining polynomials of matrices subject to updates of entries, like the one introduced in [6].

In the case of Boolean matrices, the problem can be stated as follows. Let P be a polynomial over n×n Boolean matrices with constant degree, constant number of terms, and variables X1 ... Xk . We wish to maintain a data structure for P subject to any intermixed sequence of update and query operations of the following kind:

SetRow(i, ∆X, Xb): sets to one the entries in the i-th row of variable Xb of polynomial P corresponding to one-valued entries in the i-th row of matrix ∆X.

SetCol(i, ∆X, Xb): sets to one the entries in the i-th column of variable Xb of poly- nomial P corresponding to one-valued entries in the i-th column of matrix ∆X. Reset(∆X, Xb): resets to zero the entries of variable Xb of polynomial P corresponding to one-valued entries in matrix ∆X.

Lookup(): returns the maintained value of P .

We add to the previous four operations a further update operation especially designed for maintaining path problems:

LazySet(∆X, Xb): sets to 1 the entries of variable Xb of P corresponding to one- valued entries in matrix ∆X. However, the maintained value of P might not be immediately affected by this operation.

Let CP be the correct value of P that we would have by recomputing it from scratch after each update, and let MP be the actual value that we maintain. If no Lazy Set operation is ever performed, then always MP = CP . Otherwise, MP is not necessarily equal to CP , and we guarantee the following weaker property on MP : if CP [u, v] flips from 0 to 1 due to a Set Row/Set Col operation on a variable Xb, then MP [u, v] flips from 0 to 1 as well. This means that SetRow and SetCol always correctly reveal new 1’s in the maintained value of P , possibly taking into account the 1’s inserted through previous LazySet operations. This property is crucial for dynamic path problems, since the appearance of new paths in a graph after an edge insertion, which corresponds to setting a bit to one in its adjacency matrix, is always correctly recorded in the data structure.

LEMMA 36.4 (Demetrescu and Italiano [6]) Let P be a polynomial with constant degree of matrices over the Boolean semiring. Any SetRow, SetCol, LazySet, and Reset operation on a polynomial P can be supported in O(n2) amortized time. Lookup queries are answered in optimal time.

Similar data structures can be given for settings different from the semiring of Boolean matrices. In particular, in [7] the problem of maintaining polynomials of matrices over the {min, +} semiring is addressed.

The running time of operations for maintaining polynomials in this semiring is given below.

THEOREM 36.8 (Demetrescu and Italiano [7]) Let P be a polynomial with constant degree of matrices over the {min, +} semiring. Any SetRow, SetCol, LazySet, and Reset operation on variables of P can be supported in O(D · n2) amortized time, where D is the maximum number of different values assumed by entries of variables during the sequence of operations. Lookup queries are answered in optimal time.