The randomized contractions technique, introduced by Chitnis et al. in 2012, is a robust framework for designing parameterized algorithms for graph separation problems. On a high level, an algorithm in this framework recurses on balanced separators while possible, and in the leaves of the recursion exploits the high connectivity of the graph at hand to highlight a solution using color coding. In 2014, we showed a static decomposition theorem corresponding to the recursion scheme underlying randomized contractions: given a graph G and connectivity parameter k, one can compute a tree decomposition of G with adhesions of size bounded in k and with bags exhibiting the same high connectivity properties with respect to cuts of size at most k as in the leaves of the recursion in the randomized contractions framework. This theorem was the key ingredient of the fixed-parameter algorithm for the Minimum Bisection problem. Now, we provide a new construction algorithm for tree decompositions admitting the properties described above using the notion of lean decompositions of Thomas. Our algorithm is not only arguably simpler than the one from 2014, but also gives better parameter bounds; in particular, we provide probably the best possible connectivity properties and adhesion size bounds. This allows us to provide 2^{O(k log k)} n^{O(1)}-time parameterized algorithms for Minimum Bisection, Steiner Cut, and Steiner Multicut.

Joint work with Marek Cygan, Paweł Komosa, Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh, and Magnus Wahlström.