Title: Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs,
Abstract: Connectivity related concepts are of fundamental interest in graph theory.
The area has received extensive attention over four decades, but many problems
remain unsolved, especially for directed graphs. A directed graph is
2-edge-connected (resp., 2-vertex-connected) if the removal of any edge (resp.,
vertex) leaves the graph strongly connected. In this paper we present improved
algorithms for computing the maximal 2-edge- and 2-vertex-connected subgraphs
of a given directed graph. These problems were first studied more than 35 years
ago, with $\widetilde{O}(mn)$ time algorithms for graphs with m edges and n
vertices being known since the late 1980s. In contrast, the same problems for
undirected graphs are known to be solvable in linear time. Henzinger et al.
[ICALP 2015] recently introduced $O(n^2)$ time algorithms for the directed
case, thus improving the running times for dense graphs. Our new algorithms run
in time $O(m^{3/2})$, which further improves the running times for sparse
graphs.
The notion of 2-connectivity naturally generalizes to k-connectivity for
$k>2$. For constant values of k, we extend one of our algorithms to compute the
maximal k-edge-connected in time $O(m^{3/2} \log{n})$, improving again for
sparse graphs the best known algorithm by Henzinger et al. [ICALP 2015] that
runs in $O(n^2 \log n)$ time.