Dynamic Graphs:Transitive Closure.

Transitive Closure

In the rest of this chapter we survey the newest results for dynamic problems on directed graphs. In particular, we focus on two of the most fundamental problems: transitive closure and shortest paths. These problems play a crucial role in many applications, including net- work optimization and routing, traffic information systems, databases, compilers, garbage collection, interactive verification systems, industrial robotics, dataflow analysis, and document formatting. In this section we consider the best known algorithms for fully dynamic transitive closure. Given a directed graph G with n vertices and m edges, the problem consists of supporting any intermixed sequence of operations of the following kind:

A simple-minded solution to this problem consists of maintaining the graph under insertions and deletions, searching if y is reachable from x at any query operation. This yields O(1) time per update (Insert and Delete), and O(m) time per query, where m is the current number of edges in the maintained graph.

Another simple-minded solution would be to maintain the Kleene closure of the adjacency matrix of the graph, rebuilding it from scratch after each update operation. Using the recursive decomposition of Munro [28] discussed in Section 36.3.1 and fast matrix multiplication [4], this takes constant time per reachability query and O(nω ) time per update, where ω < 2.38 is the current best exponent for matrix multiplication.

Despite many years of research in this topic, no better solution to this problem was known until 1995, when Henzinger and King [20] proposed a randomized Monte Carlo algorithm with one-sided error supporting a query time of O(n/ log n) and an amortized update time of O(nm0.58log2 n), where m is the average number of edges in the graph throughout the whole update sequence. Since m can be as high as O(n2), their update time is O(n2.16 log2 n).

Khanna, Motwani and Wilson [23] proved that, when a lookahead of Θ(n0.18) in the updates is permitted, a deterministic update bound of O(n2.18) can be achieved.

King and Sagert [25] showed how to support queries in O(1) time and updates in O(n2.26) time for general directed graphs and O(n2) time for directed acyclic graphs; their algorithm is randomized with one-sided error. The bounds of King and Sagert were further improved by King [24], who exhibited a deterministic algorithm on general digraphs with O(1) query time and O(n2 log n) amortized time per update operations, where updates are insertions of a set of edges incident to the same vertex and deletions of an arbitrary subset of edges. Using a different framework, in 2000 Demetrescu and Italiano [6] obtained a deterministic fully dynamic algorithm that achieves O(n2) amortized time per update for general directed graphs. We note that each update might change a portion of the transitive closure as large as Ω(n2). Thus, if the transitive closure has to be maintained explicitly after each update so that queries can be answered with one lookup, O(n2) is the best update bound one could hope for.

If one is willing to pay more for queries, Demetrescu and Italiano [6] showed how to break the O(n2) barrier on the single-operation complexity of fully dynamic transitive closure: building on a previous path counting technique introduced by King and Sagert [25], they devised a randomized algorithm with one-sided error for directed acyclic graphs that achieves O(n1.58) worst-case time per update and O(n0.58) worst-case time per query. Other recent results for dynamic transitive closure appear in [34, 35].

Updates in O(n2 log n) Time

In this section we address the algorithm by King [24], who devised the first deterministic near-quadratic update algorithm for fully dynamic transitive closure. The algorithm is based on the reachability tree data structure considered in Section 35.6 and on the logarithmic decomposition discussed in Section 36.3.1.

It maintains explicitly the transitive closure of a graph G in O(n2 log n) amortized time per update, and supports inserting and deleting several edges of the graph with just one operation. Insertion of a bunch of edges incident to a vertex and deletion of any subset of edges in the graph require asymptotically the same time of inserting/deleting just one edge. The algorithm maintains log n + 1 levels: level i, 0 ≤ i ≤ log n, maintains a graph Gi whose edges represent paths of length up to 2i in the original graph G. Thus, G0 = G and Glog n is the transitive closure of G.

Each level graph Gi is built on top of the previous level graph Gi−1 by keeping two trees of depth ≤ 2 rooted at each vertex v: an out-tree OU Ti(v) maintaining vertices reachable from v by traversing at most two edges in Gi−1, and an in-tree INi(v) maintaining vertices that reach v by traversing at most two edges in Gi−1. Trees INi(v) can be constructed by considering the orientation of edges in Gi−1 reversed. An edge (x, y) will be in Gi if and only if x ∈ INi(v) and y ∈ OU Ti(v) for some v. In/out trees are maintained with the deletions-only reachability tree data structure considered in Section 35.6.

To update the levels after an insertion of edges around a vertex v in G, the algorithm simply rebuilds INi(v) and OU Ti(v) for each i, 1 ≤ i ≤ log n, while other trees are not touched. This means that some trees might not be up to date after an insertion operation. Nevertheless, any path in G is represented in at least the in/out trees rooted at the latest updated vertex in the path, so the reachability information is correctly maintained. This idea is the key ingredient of King’s algorithm.

When an edge is deleted from Gi, it is also deleted from any data structures INi(v) and OU Ti(v) that contain it. The interested reader can find further details in [24].

Updates in O(n2) Time

In this section we address the algorithm by Demetrescu and Italiano [6]. The algorithm is based on the matrix data structure considered in Section 36.3.4 and on the recursive decomposition discussed in Section 36.3.1.

It maintains explicitly the transitive closure of a graph in O(n2) amortized time per update, supporting the same generalized update operations of King’s algorithm, i.e., insertion of a bunch of edges incident to a vertex and deletion of any subset of edges in the graph with just one operation. This is the best known update bound for fully dynamic transitive closure with constant query time.

The algorithm maintains the Kleene closure X∗ of the n × n adjacency matrix X of the graph as the sum of two matrices X1 and X2. Let V1 be the subset of vertices of the graph corresponding to the first half of indices of X, and let V2 contain the remaining vertices.

Both matrices X1 and X2 are defined according to Munro’s equations of Section 36.3.1, but in such a way that paths appearing due to an insertion of edges around a vertex in  V1are correctly recorded in X1, while paths that appear due to an insertion of edges around a vertex in V2 are correctly recorded in X2. Thus, neither X1 nor X2 encode complete information about X∗, but their sum does. In more detail, assuming that X is decomposed in sub-matrices A, B, C, D as explained in Section 36.3.1, and that X1, and X2 are similarly decomposed in sub-matrices E1, F1, G1, H1 and E2, F2, G2, H2, the algorithm maintains X1 and X2 with the following 8 polynomials using the data structure discussed in Section 36.3.4: