Maximal k-Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction

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-mincut 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 • minm 3/4 , n 4/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.