Computing the 3-Edge-Connected Components of Directed Graphs in Linear Time

Let G be a directed graph with m edges and n vertices. We present a deterministic linear-time algorithm for computing the 3-edge-connected components of G . This is a significant improvement over the previous best bound by Georgiadis et al. [SODA 2023], which is O~(mm−−√) and randomized. Our result is based on a novel characterization of 2-edge cuts in directed graphs and on a new technique that exploits the concept of divergent spanning trees and 2-connectivity-light graphs, and requires a careful modification of the minset-poset technique of Gabow [TALG 2016]. As a side result, our new technique yields also an oracle for providing in constant time a minimum edge-cut for any two vertices that are not 3-edge-connected. The oracle uses space O(n) and can be built in O(mlogn) time: given two query vertices, it determines in constant time whether they are 3-edge-connected, or provides a k-edge cut, with k≤2 , that separates them.