Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time

Abstract

Computing edge-connected components in directed and undirected graphs is a fundamental and well-studied problem in graph algorithms. In a very recent breakthrough, Korhonen [STOC 2025] showed that for any fixed $k$, the $k$-edge connected components of an undirected graph can be computed in linear time. In contrast, the directed case remains significantly more challenging: linear-time algorithms are only known for $k\le 3$, and for any fixed $k>3$, the best known bound for sparse or moderately dense graphs is still the $O(mn)$-time algorithm of Nagamochi and Watanabe (1993). In this paper, we break the $O(mn)$ barrier for all $k=o(n^{1/4}/\sqrt{\log n})$. We present a randomized algorithm that computes the $(k+2)$-edge-connected components of a $k$-edge-connected directed graph in $O(k^{2}m\sqrt{n}\log n)$ time, for any~$k$. This constitutes the first improvement over the classic Nagamochi--Watanabe bound for any constant $k>3$. Our approach introduces new structural insights into directed edge-cuts and combines these with both new and existing techniques. A central contribution of our work is a substantial simplification and generalization of the framework introduced in~\cite{GKPP:3ECC}, which achieved an $\tilde{O}(m\sqrt{m})$ bound for computing the $3$-edge-connected components of a digraph. In addition, we develop a variant of our algorithm that achieves the same $O(m\sqrt{n}\log n)$ running time for computing the $4$-edge-connected components of a \emph{general} directed graph.

Full version of the ICALP '26 paper