Parameterized Domination in Circle Graphs |
| |
Authors: | Nicolas Bousquet Daniel Gonçalves George B Mertzios Christophe Paul Ignasi Sau Stéphan Thomassé |
| |
Affiliation: | 1. AlGCo project-team, CNRS, LIRMM, Montpellier, France 2. School of Engineering and Computing Sciences, Durham University, Durham, UK 3. Laboratoire LIP, U. Lyon, CNRS, ENS Lyon, INRIA, UCBL, Lyon, France
|
| |
Abstract: | A circle graph is the intersection graph of a set of chords in a circle. Keil Discrete Appl. Math., 42(1):51–63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction: - Dominating Set, Independent Dominating Set, Connected Dominating Set, Total Dominating Set, and Acyclic Dominating Set are W1]-hard in circle graphs, parameterized by the size of the solution.
- Whereas both Connected Dominating Set and Acyclic Dominating Set are W1]-hard in circle graphs, it turns out that Connected Acyclic Dominating Set is polynomial-time solvable in circle graphs.
- If T is a given tree, deciding whether a circle graph G has a dominating set inducing a graph isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by t=|V(T)|. We prove that the FPT algorithm runs in subexponential time, namely $2^{\mathcal{O}(t \cdot\frac{\log\log t}{\log t})} \cdot n^{\mathcal{O}(1)}$ , where n=|V(G)|.
|
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|