Nearly Work-Efficient Parallel DFS in Undirected Graphs

Abstract

We present the first parallel depth-first search algorithm for undirected graphs that has near-linear work and sublinear depth. Concretely, in any \(n\)-node \(m\)-edge undirected graph, our algorithm computes a DFS in \(\tilde{O}(\sqrt{n})\) depth and using \(\tilde{O}(m+n)\) work. All prior work either required \(\Omega(n)\) depth, and thus were essentially sequential, or needed a high \(poly(n)\) work and thus were far from being work-efficient.