The dominating set problem in geometric intersection graphs
- ,
- Sándor Kisfaludi-Bak,
- Gerhard Woeginger
- ,
- ,
- RWTH Aachen University
Open access
Information
Output type
Original language
EnglishPages from-to (Number of pages)
Pages 14:1-14:12Publication milestones
- Published - 01/02/2018
Publication status
Place of publication
DagstuhlPublisher
Schloss Dagstuhl - Leibniz-Zentrum für InformatikPublication series
- Publication series name: LIPIcs
Volume: 89
ISBN (Print)
978-3-95977-051-4Host publication title
12th International Symposium on Parameterized and Exact Computation, IPEC 2017Related Event
Title
Event type
ConferenceDegree of recognition
International eventDate
06/09/2017 - 08/09/2017Location
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.
