License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2017.14
URN: urn:nbn:de:0030-drops-85538
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8553/
Go to the corresponding LIPIcs Volume Portal

de Berg, Mark ; Kisfaludi-Bak, Sándor ; Woeginger, Gerhard

The Dominating Set Problem in Geometric Intersection Graphs

pdf-format:
LIPIcs-IPEC-2017-14.pdf (0.8 MB)

Abstract

We study the parameterized complexity of dominating sets in geometric intersection graphs. In one dimension, we investigate intersection graphs induced by translates of a fixed pattern Q that consists of a finite number of intervals and a finite number of isolated points. We prove that Dominating Set on such intersection graphs is polynomially solvable whenever Q contains at least one interval, and whenever Q contains no intervals and for any two point pairs in Q the distance ratio is rational. The remaining case where Q contains no intervals but does contain an irrational distance ratio is shown to be NP-complete and contained in FPT (when parameterized by the solution size). In two and higher dimensions, we prove that Dominating Set is contained in W[1] for intersection graphs of semi-algebraic sets with constant description complexity. This generalizes known results from the literature. Finally, we establish W[1]-hardness for a large class of intersection graphs.

BibTeX - Entry

@InProceedings{deberg_et_al:LIPIcs:2018:8553,
  author =	{Mark de Berg and S{\'a}ndor Kisfaludi-Bak and Gerhard Woeginger},
  title =	{{The Dominating Set Problem in Geometric Intersection Graphs}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Daniel Lokshtanov and Naomi Nishimura},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8553},
  URN =		{urn:nbn:de:0030-drops-85538},
  doi =		{10.4230/LIPIcs.IPEC.2017.14},
  annote =	{Keywords: dominating set, intersection graph, W-hierarchy}
}

Keywords: dominating set, intersection graph, W-hierarchy
Collection: 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Issue Date: 2018
Date of publication: 02.03.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI