Computing the 3-Edge-Connected Components of Directed Graphs in Linear Time
Loukas Georgiadis, Giuseppe Francesco Italiano, Evangelos Kosinas · 2024
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$\tilde{O}(m\sqrt{m})$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(m\log n)$time: given two query vertices, it determines in constant time whether they are 3-edge-connected, or provides a k-edge cut, with$k\leq 2$, that separates them.