Skip to main content

Research Repository

Advanced Search

Parameterized Domination in Circle Graphs

Bousquet, N.; Gonçalves, D.; Mertzios, G.B.; Paul, C.; Sau, I.; Thomassé, S.

Parameterized Domination in Circle Graphs Thumbnail


Authors

N. Bousquet

D. Gonçalves

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 Mar 28, 2024
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





You might also like



Downloadable Citations