Near Optimal Parallel Algorithms for Dynamic DFS in Undirected Graphs

摘要

Depth first search (DFS) tree is a fundamental data structure for solving various graph problems. The classical algorithm [54] for building a DFS tree requires O(m + n) time for a given undirected graph G having n vertices and m edges. Recently, Baswana et al. [5] presented a simple algorithm for updating the DFS tree of an undirected graph after an edge/vertex update in O(n)1 time. However, their algorithm is strictly sequential. We present an algorithm achieving similar bounds that can be easily adopted to the parallel environment. In the parallel environment, a DFS tree can be computed from scratch in expected O(1) time [2] on an EREW PRAM, whereas the best deterministic algorithm takes O(n~(1/2)) time [2, 27] on a CRCW PRAM. Our algorithm can be used to develop optimal time (to poly log n factors) deterministic parallel algorithms for maintaining fully dynamic DFS and fault tolerant DFS of an undirected graph. (1) Parallel Fully Dynamic DFS: Given an arbitrary online sequence of vertex or edge updates, we can maintain a DFS tree of an undirected graph in O(1) time per update using m processors on an EREW PRAM. (2) Parallel Fault tolerant DFS: An undirected graph can be preprocessed to build a data structure of size 0(m), such that for any set of k updates (where k is constant) in the graph, a DFS tree of the updated graph can be computed in O(1) time using n processors on an EREW PRAM. For constant k, this is also work optimal (to poly log n factors). Moreover, our fully dynamic DFS algorithm provides, in a seamless manner, nearly optimal (to poly log n factors) algorithms for maintaining a DFS tree in the semi-streaming environment and a restricted distributed model. These are the first parallel, semi-streaming, and distributed algorithms for maintaining a DFS tree in the dynamic setting.