Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More

We present 𝑘 O (𝑘 2 ) 𝑚 time algorithms for various problems about decomposing a given undirected graph by edge cuts or vertex separators of size < 𝑘 into parts that are "well-connected" with respect to cuts or separators of size < 𝑘; here, 𝑚 is the total number of vertices and edges of the graph. As an application of our results, we obtain for every fixed 𝑘 a linear-time algorithm for computing the 𝑘-edgeconnected components of a given graph, solving a long-standing open problem. More generally, we obtain a 𝑘 O (𝑘 2 ) 𝑚 time algorithm for computing a 𝑘-Gomory-Hu tree of a given graph, which is a structure representing pairwise minimum cuts of size < 𝑘. Our main technical result, from which the other results follow, is a 𝑘 O (𝑘 2 ) 𝑚 time algorithm for computing a 𝑘-lean tree decomposition of a given graph. This is a tree decomposition with adhesion size < 𝑘 that captures the existence of separators of size < 𝑘 between subsets of its bags. A 𝑘-lean tree decomposition is also an unbreakable tree decomposition with optimal unbreakability parameters for the adhesion size bound 𝑘. As further applications, we obtain 𝑘 O (𝑘 2 ) 𝑚 time algorithms for 𝑘-vertex connectivity and for element connectivity 𝑘-Gomory-Hu tree. All of our algorithms are deterministic. Our techniques are inspired by the tenth paper of the Graph Minors series of Robertson and Seymour and by Bodlaender's parameterized linear-time algorithm for treewidth. CCS Concepts • Theory of computation → Graph algorithms analysis; Parameterized complexity and exact algorithms.