Intractability of Clique-Width Parameterizations

2010/01/01 by Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov +1 · 78 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Protein Degradation and Inhibitors #Parameterized complexity #Combinatorics #Mathematics #Clique #Vertex (graph theory) #Clique problem #Clique graph #Discrete mathematics #Treewidth #Graph #Hamiltonian path #Split graph #Independent set #Chordal graph #Pathwidth #Graph power #Line graph #1-planar graph

paper · doi:10.1137/080742270

published in SIAM Journal on Computing 39(5), 1941-1956 (Society for Industrial and Applied Mathematics)

openalex publication_date 2010/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15

Abstract

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)⋅ 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≠ W[1]).

Citations

• Parameterized Complexity Theory
• Upper bounds to the clique width of graphs
• k-NLC graphs and polynomial algorithms
• Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Approximating clique-width and branch-width
• A partial k-arboretum of graphs with bounded treewidth
• On the Relationship Between Clique-Width and Treewidth
• Finding Branch-Decompositions and Rank-Decompositions
• Approximating rank-width and clique-width quickly

Cited by

• Clique-width [wikipedia]