Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh · SIAM Journal on Computing · 2014
We obtain asymptotically tight algorithmic bounds for Max-Cut and Edge Dominating Set problems on graphs of bounded clique-width. We show that on an $n$-vertex graph of clique-width $t$ both problems (1) cannot be solved in time $f(t)n^{o(t)}$ for any function $f$ of $t$ unless exponential time hypothesis fails, and (2) can be solved in time $n^{O(t)}$.