On Dynamic DFS Tree in Directed Graphs

Let G = (V, E) be a directed graph on n vertices and m edges. We address the problem of maintaining a depth first search (DFS) tree efficiently under insertion/deletion of edges in G. 1. We present an efficient randomized decremental algorithm for maintaining a DFS tree for a directed acyclic graph. For processing any arbitrary online sequence of edge deletions, this algorithm takes expected O (mn log n) time. 2. We present the following lower bound results. (a) Any decremental (or incremental) algorithm for maintaining the ordered DFS tree explicitly requires f/(mn) total update time in the worst case. (b) Any decremental (or incremental) algorithm for maintaining the ordered DFS tree is at least as hard as computing all-pairs reach ability in a directed graph.