Randomized Contractions Meet Lean Decompositions

We show an algorithm that, given an n-vertex graph G and a parameter k, in time 2O(k log k) n O(1) finds a tree decomposition of G with the following properties: — every adhesion of the tree decomp...