Randomized contractions meet lean decompositions

Marek Cygan, Paweł Komosa, Daniel Lokshtanov +4

We show an algorithm that, given an $n$-vertex graph $G$ and a parameter $k$, in time $2^{O(k\log k)}{n}^{O(1)}$ finds a tree decomposition of $G$ with the following properties: *…