2026-07-20T02:19:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8553 2024-03-06T10:41:31Z ddc:004 open_access

The Dominating Set Problem in Geometric Intersection Graphs de Berg, Mark Kisfaludi-Bak, Sándor Woeginger, Gerhard dominating set intersection graph W-hierarchy 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mark de Berg and Sándor Kisfaludi-Bak and Gerhard Woeginger 2018 Is Part Of LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2017.14 urn:nbn:de:0030-drops-85538 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.14 eng https://creativecommons.org/licenses/by/3.0/legalcode