We present a faster algorithm for finding a minimum dijoin, a smallest set of edges whose contraction makes a directed graph strongly connected. This problem has been studied since the 1960s [Seshu and Reed 1961] and is dual to finding a maximum sized family of disjoint dicuts [Lucchesi and Younger 1978]. Given a directed graph G with n vertices and m edges whose minimum dijoin has size d, our algorithm outputs both a minimum dijoin and a maximum sized family of disjoint dicuts in O(TC⋅ d) time, where TC = min(mn,n^ω) is the time to compute the transitive closure. This improves upon the state of the art of [Gabow 1993], which requires O(TC ⋅ min(m^{1/2},n^{2/3})) time when d = o(min(m^{1/2},n^{2/3})). Our result extends to finding a minimum weighted dijoin. We achieve this by observing that Frank’s algorithm [Frank 1981] can be sped up when warm-started with a 2-approximation solution, which we observed can be computed in near-linear time.

Peer Reviewed

The maximal k-edge-connected subgraphs problem is a classical graph clustering problem studied since the 70's. Surprisingly, no non-trivial technique for this problem in weighted graphs is known: a very straightforward recursive-min-cut algorithm with Ω(mn) time has remained the fastest algorithm until now. All previous progress gives a speed-up only when the graph is unweighted, and k is small enough (e.g. Henzinger et al. (ICALP'15), Chechik et al. (SODA'17), and Forster et al. (SODA'20)). We give the first algorithm that breaks through the long-standing Õ(mn)-time barrier in weighted undirected graphs. More specifically, we show a maximal k-edge-connected subgraphs algorithm that takes only Õ(m · min{m3/4,n4/5}) time. As an immediate application, we can (1 + ε)-approximate the strength of all edges in undirected graphs in the same running time. Our key technique is the first local cut algorithm with exact cut-value guarantees whose running time depends only on the output size. All previous local cut algorithms either have running time depending on the cut value of the output, which can be arbitrarily slow in weighted graphs or have approximate cut guarantees.