Intractability of Clique-Width Parameterizations
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh · SIAM Journal on Computing · 2010
We show that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are $W[1]$-hard parameterized by clique-width. It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when parameterized by the clique-width, that is, solvable in time $g(k)\cdot n^{O(1)}$ on n-vertex graphs of clique-width k, where g is some function of k only. Our results imply that the running time $O(n^{f(k)})$ of many clique-width-based algorithms is essentially the best we can hope for (up to a widely believed assumption from parameterized complexity, namely $FPT eq W[1]$).