Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
Tuukka Korhonen · 2025
We present kO(k2) m time algorithms for various problems about decomposing a given undirected graph by edge cuts or vertex separators of size O(k2) m time algorithm for computing a k-Gomory-Hu tree of a given graph, which is a structure representing pairwise minimum cuts of size O(k2) m time algorithm for computing a k-lean tree decomposition of a given graph. This is a tree decomposition with adhesion size O(k2) m time algorithms for k-vertex connectivity and for element connectivity k-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.