The complexity of Dominating set in geometric intersection graphs

Research output: Contribution to journalArticleAcademicpeer-review

3 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

Fingerprint

Geometric Graphs
Intersection Graphs
Dominating Set
Interval
Semi-algebraic Sets
Parameterized Complexity
Hardness
One Dimension
Higher Dimensions
Two Dimensions
NP-complete problem
Unit

Keywords

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

Cite this

@article{7b29e7ad2d11491fa1d13eed1ded6bd6,
title = "The complexity of Dominating set in geometric intersection graphs",
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.",
keywords = "Dominating Set, Geometric intersection graph, Semi-algebraic set, W-hierarchy",
author = "{de Berg}, Mark and S{\'a}ndor Kisfaludi-Bak and Gerhard Woeginger",
year = "2019",
month = "5",
day = "17",
doi = "10.1016/j.tcs.2018.10.007",
language = "English",
volume = "769",
pages = "18--31",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

The complexity of Dominating set in geometric intersection graphs. / de Berg, Mark; Kisfaludi-Bak, Sándor (Corresponding author); Woeginger, Gerhard.

In: Theoretical Computer Science, Vol. 769, 17.05.2019, p. 18-31.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - The complexity of Dominating set in geometric intersection graphs

AU - de Berg, Mark

AU - Kisfaludi-Bak, Sándor

AU - Woeginger, Gerhard

PY - 2019/5/17

Y1 - 2019/5/17

N2 - 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.

AB - 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.

KW - Dominating Set

KW - Geometric intersection graph

KW - Semi-algebraic set

KW - W-hierarchy

UR - http://www.scopus.com/inward/record.url?scp=85054885234&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2018.10.007

DO - 10.1016/j.tcs.2018.10.007

M3 - Article

AN - SCOPUS:85054885234

VL - 769

SP - 18

EP - 31

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -