Parameterized Domination in Circle Graphs

DOI10.1007/978-3-642-34611-8_31MaRDI QIDQ5200517zbMATH OpenOpenAlexFDO

Authors Daniel Gonçalves, George B. Mertzios, Christophe Paul, Ignasi Sau, Nicolas Bousquet, Stéphan Thomassé

Publication date 6 November 2012

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.3728, http://dro.dur.ac.uk/15246/1/15246.pdf

zbMATH Keywords

dynamic programmingparameterized complexityparameterized algorithmscircle graphsdomination problemsconstrained domination

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parallel algorithms in computer science (68W10)

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.

Recommendations

• Parameterized domination in circle graphs
• The complexity of domination problems in circle graphs
• Domination in circulant graphs
• scientific article; zbMATH DE number 6120615
• Domination in generalized circulant graphs
• Efficient domination in circulant graphs
• Total domination in circular-arc graphs
• scientific article; zbMATH DE number 1124603
• Efficient and perfect domination on circular-arc graphs

Cited in

(8)

• Parameterized domination in circle graphs
• On dominating set of some subclasses of string graphs
• On dominating set polyhedra of circular interval graphs
• scientific article; zbMATH DE number 2170424 (Why is no real title available?)
• scientific article; zbMATH DE number 6120615 (Why is no real title available?)
• scientific article; zbMATH DE number 6119094 (Why is no real title available?)
• Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
• The complexity of domination problems in circle graphs

This page was built for publication: Parameterized Domination in Circle Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5200517)