Parameterized Domination in Circle Graphs

DOI10.1007/978-3-642-34611-8_31zbMATH Open1341.05184arXiv1205.3728OpenAlexW2144834624MaRDI QIDQ5200517FDOQ5200517

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)

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.

Full work available at URL: https://arxiv.org/abs/1205.3728

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

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)

Cited In (8)

• Parameterized domination in circle graphs
• The complexity of domination problems in circle graphs
• Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
• On dominating set of some subclasses of string graphs
• On dominating set polyhedra of circular interval graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

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)