Virtual Discrete Math Colloquium

We show that there is no $2^{o(k^2)}{n}^{O(1)}$ time algorithm for Independent Set on $n$-vertex graphs with rank-width $k$, unless the Exponential Time Hypothesis (ETH) fails. Our lower bound matches the $2^{O(k^2)}{n}^{O(1)}$ time algorithm given by Bui-Xuan, Telle, and Vatshelle and it answers the open question of Bergougnoux and Kanté . We also show …