de Berg, Mark ;
KisfaludiBak, Sándor ;
Woeginger, Gerhard
The Dominating Set Problem in Geometric Intersection Graphs
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 NPcomplete 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 semialgebraic 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 KisfaludiBak 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:114:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770514},
ISSN = {18688969},
year = {2018},
volume = {89},
editor = {Daniel Lokshtanov and Naomi Nishimura},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8553},
URN = {urn:nbn:de:0030drops85538},
doi = {10.4230/LIPIcs.IPEC.2017.14},
annote = {Keywords: dominating set, intersection graph, Whierarchy}
}
2018
Keywords: 

dominating set, intersection graph, Whierarchy 
Seminar: 

12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Issue date: 

2018 
Date of publication: 

2018 