N. Bousquet
Parameterized Domination in Circle Graphs
Bousquet, N.; Gonçalves, D.; Mertzios, G.B.; Paul, C.; Sau, I.; Thomassé, S.
Authors
D. Gonçalves
Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
C. Paul
I. Sau
S. Thomassé
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 W[1]-hard in circle graphs, parameterized by the size of the solution. Whereas both Connected Dominating Set and Acyclic Dominating Set are W[1]-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 2O(t⋅loglogtlogt)⋅nO(1), where n=|V(G)|.
Citation
Bousquet, N., Gonçalves, D., Mertzios, G., Paul, C., Sau, I., & Thomassé, S. (2014). Parameterized Domination in Circle Graphs. Theory of Computing Systems, 54(1), 45-72. https://doi.org/10.1007/s00224-013-9478-8
Journal Article Type | Article |
---|---|
Publication Date | Jan 1, 2014 |
Deposit Date | Sep 5, 2014 |
Publicly Available Date | Sep 16, 2014 |
Journal | Theory of Computing Systems |
Print ISSN | 1432-4350 |
Electronic ISSN | 1433-0490 |
Publisher | Springer |
Peer Reviewed | Peer Reviewed |
Volume | 54 |
Issue | 1 |
Pages | 45-72 |
DOI | https://doi.org/10.1007/s00224-013-9478-8 |
Keywords | Circle graphs, Domination problems, Parameterized complexity, Parameterized algorithms, Dynamic programming, Constrained domination. |
Files
Accepted Journal Article
(236 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/s00224-013-9478-8.
You might also like
Fast parameterized preprocessing for polynomial-time solvable graph problems
(2023)
Journal Article
Computing maximum matchings in temporal graphs
(2023)
Journal Article
Payment scheduling in the Interval Debt Model
(2023)
Conference Proceeding
The complexity of growing a graph
(2022)
Conference Proceeding
Interference-free walks in time: Temporally disjoint paths
(2022)
Journal Article