The complexity of Dominating set in geometric intersection graphs

Mark de Berg, Sándor Kisfaludi-Bak (Corresponding author), Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)

Abstract

We study the parameterized complexity of the dominating set problem 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. So far this was only known for unit squares. Finally, we establish W[1]-hardness for a large class of intersection graphs.

Original languageEnglish
Pages (from-to)18-31
Number of pages14
JournalTheoretical Computer Science
Volume769
DOIs
Publication statusPublished - 17 May 2019

Keywords

  • Dominating Set
  • Geometric intersection graph
  • Semi-algebraic set
  • W-hierarchy

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

Cite this