The dominating set problem in geometric intersection graphs

Mark De Berg, Sándor Kisfaludi-Bak, Gerhard Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
38 Downloads (Pure)


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.

Original languageEnglish
Title of host publication12th International Symposium on Parameterized and Exact Computation, IPEC 2017
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Print)978-3-95977-051-4
Publication statusPublished - 1 Feb 2018
Event12th International Symposium on Parameterized and Exact Computation (IPEC 2017) - Vienna, Austria
Duration: 6 Sep 20178 Sep 2017
Conference number: 12

Publication series



Conference12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Abbreviated titleIPEC 2017
Internet address


  • Dominating set
  • Intersection graph
  • W-hierarchy


Dive into the research topics of 'The dominating set problem in geometric intersection graphs'. Together they form a unique fingerprint.

Cite this