Parameterized Domination in Circle Graphs

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.
Type de document :
Communication dans un congrès
WG'12: 38th International Workshop on Graph Theoretic Concepts in Computer Science, Jun 2012, Jerusalem, Israel. LNCS (7551), pp.308-319, 2012, Graph-Theoretic Concepts in Computer Science. 〈https://sites.google.com/site/wg2012conf/〉. 〈10.1007/978-3-642-34611-8_31〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00738534
Contributeur : Daniel Gonçalves <>
Soumis le : jeudi 4 octobre 2012 - 15:09:50
Dernière modification le : jeudi 31 mai 2018 - 14:54:03

Lien texte intégral

Identifiants

Citation

Nicolas Bousquet, Daniel Gonçalves, George Mertzios, Christophe Paul, Ignasi Sau, et al.. Parameterized Domination in Circle Graphs. WG'12: 38th International Workshop on Graph Theoretic Concepts in Computer Science, Jun 2012, Jerusalem, Israel. LNCS (7551), pp.308-319, 2012, Graph-Theoretic Concepts in Computer Science. 〈https://sites.google.com/site/wg2012conf/〉. 〈10.1007/978-3-642-34611-8_31〉. 〈lirmm-00738534〉

Partager

Métriques

Consultations de la notice

205