Space-Efficient DFS and Applications: Simpler, Leaner, Faster

The problem of space-efficient depth-first search (DFS) is reconsidered. A particularly simple and fast algorithm is presented that, on a directed or undirected input graph $G=(V,E)$ with $n$ vertices and $m$ edges, carries out a DFS in $O(n+m)$ time with $n+\sum_{v\in V_{\ge 3}}\lceil{\log_2(d_v-1)}\rceil +O(\log n)\le n+m+O(\log n)$bitsofworkingmemory,where$d_v$ is the (total) degree of $v$, for each $v\in V$, and $V_{\ge 3}={v\in V\mid d_v\ge 3}$. A slightly more complicated variant of the algorithm works in the same time with at most $n+(4\mathrm{/}5)m+O(\log n)$ bits. It is also shown that a DFS can be carried out in a graph with $n$ vertices and $m$ edges in $O(n+m{\log }^{\ast }\text{\hspace{0.17em}⁣}n)$ time with $O(n)$ bits or in $O(n+m)$ time with either $O(n\log \log (4+m\mathrm{/}n))$ bits or, for arbitrary integer $k\ge 1$, $O(n{\log }^{(k)}\text{\hspace{0.17em}⁣}n)$ bits. These results among them subsume or improve most earlier results on space-efficient DFS. Some of the new time and space bounds are shown to extend to applications of DFS such as the computation of cut vertices, bridges, biconnected components and 2-edge-connected components in undirected graphs.