W[1]-hardness of some domination-like problems parameterized by tree-width
| Autor: | Chapelle, Mathieu |
|---|---|
| Rok vydání: | 2010 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | The concept of generalized domination unifies well-known variants of domination-like and independence problems, such as Dominating Set, Independent Set, Perfect Code, etc. A generalized domination (also called $[\sigma,\rho]$-Dominating Set}) problem consists in finding a subset of vertices in a graph such that every vertex is satisfied with respect to two given sets of constraints $\sigma$ and $\rho$. Very few problems are known not to be FPT when parameterized by tree-width, as usually this restriction allows one to write efficient algorithms to solve the considered problems. The main result of this article is a proof that for some (infinitely many) sets $\sigma$ and $\rho$, the problem $\exists[\sigma,\rho]$-Dominating Set} is W[1]-hard when parameterized by the tree-width of the input graph. This contrasts with the current knowledge on the parameterized complexity of this problem when parameterized by tree-width, which had only been studied for finite and cofinite sets $\sigma$ and $\rho$ and for which it has been shown to be FPT. Comment: Updated and corrected version; submitted to Theoretical Computer Science |
| Databáze: | arXiv |
| Externí odkaz: |
|