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é



Contributors

Martin Charles . Golumbic
Editor

Michal Stern
Editor

Avivit Levy
Editor

Gila Morgenstern
Editor

Abstract

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Applied Mathematics, 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 has a dominating set isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by |V(T)|. We prove that the FPT algorithm is subexponential.

Citation

Bousquet, N., Gonçalves, D., Mertzios, G., Paul, C., Sau, I., & Thomassé, S. (2012). Parameterized Domination in Circle Graphs. In M. C. .. Golumbic, M. Stern, A. Levy, & G. Morgenstern (Eds.), Graph-theoretic concepts in computer science : 38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012 ; revised selected papers (308-319). https://doi.org/10.1007/978-3-642-34611-8_31

Conference Name 38th International Workshop, WG 2012
Conference Location Jerusalem, Israel
Publication Date Jun 28, 2012
Deposit Date Sep 5, 2014
Publicly Available Date Mar 28, 2024
Volume 7551
Pages 308-319
Series Title Lecture notes in computer science
Series Number 7551
Series ISSN 0302-9743,1611-3349
Book Title Graph-theoretic concepts in computer science : 38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012 ; revised selected papers
ISBN 9783642346101
DOI https://doi.org/10.1007/978-3-642-34611-8_31
Keywords Circle graphs, Domination problems, Parameterized complexity, Parameterized algorithms, Dynamic programming, Constrained domination
Public URL https://durham-repository.worktribe.com/output/1154526

Files





You might also like



Downloadable Citations