Biconnectivity, $st$-numbering and other applications of DFS using $O(n)$ bits

Abstract

We consider space efficient implementations of some classical applications of DFS including the problem of testing biconnectivity and $2$-edge connectivity, finding cut vertices and cut edges, computing chain decomposition and $st$-numbering of a given undirected graph $G$ on $n$ vertices and $m$ edges. Classical algorithms for them typically use DFS and some $\Omega (\lg n)$ bits\footnote{We use $\lg$ to denote logarithm to the base $2$.} of information at each vertex. Building on a recent $O(n)$-bits implementation of DFS due to Elmasry et al. (STACS 2015) we provide $O(n)$-bit implementations for all these applications of DFS. Our algorithms take $O(m{\lg }^{c}n\lg \lg n)$ time for some small constant $c$ (where $c\le 2$). Central to our implementation is a succinct representation of the DFS tree and a space efficient partitioning of the DFS tree into connected subtrees, which maybe of independent interest for designing other space efficient graph algorithms.

18 pages, 4 figures, Preliminary version of this article appeared in the proceedings of 27th ISAAC 2016, Journal version is accepted to JCSS and will soon appear