Improved Dynamic Reachability Algorithms for Directed Graphs

We obtain several new dynamic algorithms for maintaining the transitive closure of a directed graph, and several other algorithms for answering reachability queries without explicitly maintaining a transitive closure matrix. Among our algorithms are: (i) a decremental algorithm for maintaining the transitive closure of a directed graph, through an arbitrary sequence of edge deletions, in O(mn) total expected time, essentially the time needed for computing the transitive closure of the initial graph. Such a result was previously known only for acyclic graphs; (ii) two fully dynamic algorithms for answering reachability queries. The first is deterministic and has an amortized insert/delete time of O(m/spl radic/n), and worst-case query time of O(/spl radic/n). The second is randomized and has an amortized insert/delete time of O(m/sup 0. 58/n) and worst-case query time of O(m/sup 0. 43/). This significantly improves the query times of algorithms with similar update times; and (iii) a fully dynamic algorithm for maintaining the transitive closure of an acyclic graph. The algorithm is deterministic and has a worst-case insert time of O(m), constant amortized delete time of O(1), and a worst-case query time of O(n/ log n). Our algorithms are obtained by combining several new ideas, one of which is a simple sampling idea used for detecting decompositions of strongly connected components, with techniques of Even and Shiloach (1981), Italiano (1988), Henzinger and King (1995), and Frigioni et al. (2001). We also adapt results of Cohen (1997) on estimating the size of the transitive closure to the dynamic setting.

Authors

• Liam Roditty
• Uri Zwick

Keywords

• Heuristic algorithms
• Monte Carlo methods
• Computer science
• Sampling methods
• Costs
• Directed Graph
• Dynamic Algorithm
• Reachability Algorithm
• Deterministic
• Acyclic Graph
• Update Time
• Query Time
• Worst-case Time
• Transitive Closure
• Data Structure
• Path Length
• Insertion Sequences
• Matrix Multiplication
• Total Run Time
• Beginning Of Phase
• Vertices
• Monte Carlo Algorithm
• Components Of The Graph
• Graph Algorithms
• Update Operation