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é
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
Accepted Conference Proceeding
(238 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-34611-8_31
You might also like
Graphs with minimum fractional domatic number
(2023)
Journal Article
Approximate and Randomized algorithms for Computing a Second Hamiltonian Cycle
(2023)
Journal Article
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs
(2023)
Conference Proceeding
Fast parameterized preprocessing for polynomial-time solvable graph problems
(2023)
Journal Article
The complexity of computing optimum labelings for temporal connectivity
(2022)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search