Fomin, Fedor V. ; Golovach, Petr A. ; Lokshtanov, Daniel ; Saurabh, Saket (2010) Intractability of Clique-Width Parameterizations SIAM Journal on Computing, 39 (5). pp. 1941-1956. ISSN 0097-5397
Full text not available from this repository.
Official URL: http://doi.org/10.1137/080742270
Related URL: http://dx.doi.org/10.1137/080742270
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 F P T 6= W[1]).
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Society for Industrial and Applied Mathematics. |
| ID Code: | 123473 |
| Deposited On: | 20 Sep 2021 10:42 |
| Last Modified: | 20 Sep 2021 10:42 |
Repository Staff Only: item control page
