Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs
  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.
