Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Parameterized domination in circle graphs.

Bousquet, N. and Gonçalves, D. and Mertzios, G.B. and Paul, C. and Sau, I. and Thomassé, S. (2012) 'Parameterized domination in circle graphs.', in Graph-theoretic concepts in computer science : 38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012 ; revised selected papers. Berlin, Heidelberg: Springer, pp. 308-319. Lecture notes in computer science., 7551 (7551).

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.

Item Type:Book chapter
Keywords:Circle graphs, Domination problems, Parameterized complexity, Parameterized algorithms, Dynamic programming, Constrained domination
Full text:(AM) Accepted Manuscript
Download PDF
(233Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1007/978-3-642-34611-8_31
Publisher statement:The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-34611-8_31
Date accepted:No date available
Date deposited:24 April 2015
Date of first online publication:2012
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar