Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time

Abstract

We present faster algorithms for computing the 2-edge and 2-vertex strongly connected components of a directed graph, which are straightforward generalizations of strongly connected components. While in undirected graphs the 2-edge and 2-vertex connected components can be found in linear time, in directed graphs only rather simple $O(mn)$-time algorithms were known. We use a hierarchical sparsification technique to obtain algorithms that run in time $O(n^2)$. For 2-edge strongly connected components our algorithm gives the first running time improvement in 20 years. Additionally we present an $O(m^2/\log n)$-time algorithm for 2-edge strongly connected components, and thus improve over the $O(mn)$ running time also when $m=O(n)$. Our approach extends to k-edge and k-vertex strongly connected components for any constant k with a running time of $O(n^2{\log }^{2}n)$ for edges and $O(n^3)$ for vertices.

References in corpus (1)

• On computing the $2$-vertex-connected components of directed graphs

Cited by in corpus (7)

• Finding Densest $k$-Connected Subgraphs
• Computing $2$-twinless blocks
• Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs
• Fine-Grained Complexity and Conditional Hardness for Sparse Graphs
• Strong Connectivity in Directed Graphs under Failures, with Application
• Decremental Single-Source Reachability in Planar Digraphs
• An Experimental Study of Dynamic Dominators