Faster Computation of 3-Edge-Connected Components in Digraphs

We present an Õ(m3/2) time randomized (Monte Carlo) algorithm for computing the 3-edge-connected components of a digraph with m edges and n vertices. This constitutes the first improvement since the algorithm of Nagamochi & Watanabe from 1993, which runs in O(m · n) time. Thus, our algorithm is the first that overcomes the run-time of O(n) computations of 3-bounded max-flows (that is, computations of the value minFlow(s,t), 3 for O(n) pairs s-t). Our algorithm involves a combination of known and new techniques together with new structural insights on the interactions between directed min-cuts. One novel aspect that we introduce is an efficient graph operation G for replacing a set of vertices S that is disconnected from Vby an edge-cut of size 2 (2-out set), with a gadget of small size that preserves the pairwise connectivity among the vertices of V. Another main ingredient of our approach is an extension of the framework for computing the vertex-connectivity (or edge-connectivity) in a digraph [Nanongkai et al., STOC'19]. This extension allows us to efficiently identify either all small 2-out sets of vertices, or identify enough 2-out sets whose total internal volume is a constant fraction of the edges of the graph. Repeatedly replacing each identified 2-out set S with a small gadget (using the G and G operations) either shrinks the size of the graph by a constant fraction, or concludes that no small 2-out set exists. We believe that our techniques may be of independent interest. Finally, we augment our algorithm with a data structure that can report in constant time the edges of some edge-cut of size at most 2 that disconnects any two query vertices u,v, or report in constant time that no such edge-cut exists.