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 …