INTRACTABILITY OF CLIQUE-WIDTH PARAMETERIZATIONS.

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) · nO(1) on η-vertex graphs of clique-width k, where g is some function of k only. Our results imply that the running time O(nf(k)) of many clique-widthbased algorithms is essentially the best we can hope for (up to a widely believed assumption from parameterized complexity, namely FPT ≠ W[1]). [ABSTRACT FROM AUTHOR]