DYNAMIC DFS IN UNDIRECTED GRAPHS: BREAKING THE O(m) BARRIER

Depth first search (DFS) tree is a fundamental data structure for solving various problems in graphs. It is well known that it takes O(m+n) time to build a DFS tree for a given undirected graph G = (V, E) on n vertices and m edges. We address the problem of maintaining a DFS tree when the graph is undergoing updates (insertion and deletion of vertices or edges). We present the following results for this problem: (1) Fault tolerant DFS tree: There exists a data structure of size (O) over tilde (m) (where (O) over tilde() hides the polylogarithmic factors) which can be preprocessed in (O) over tilde (m) time such that given any set G\F of failed vertices or edges, a DFS tree of the graph G\T can be reported in (O) over tilde (n vertical bar F vertical bar) time. (2) Fully dynamic DFS tree: There exists a fully dynamic algorithm for maintaining a DFS tree that takes (O) over tilde (m) time for preprocessing and worst case (O) over tilde(root mn) time per update for any arbitrary online sequence of updates. (3) Incremental DFS tree: There exists an incremental algorithm for maintaining a DFS tree that takes (O) over tilde (m) time for preprocessing and worst case (O) over tilde (n) time per update for any arbitrary online sequence of edge insertion. These are the first o(m) worst case time results for maintaining a DFS tree of a dense graph in a dynamic environment. Moreover, our fully dynamic algorithm provides, in a seamless manner, the first deterministic algorithm for dense graphs with O(1) query time and o(m) worst case update time for connectivity, biconnectivity, and 2-edge connectivity in the dynamic subgraph model.