The dominating set problem in geometric intersection graphs

DOI10.4230/LIPICS.IPEC.2017.14zbMATH Open1443.68126arXiv1709.05182OpenAlexW2964281516MaRDI QIDQ5111873FDOQ5111873

Authors: Sándor Kisfaludi-Bak, Gerhard J. Woeginger, Mark de Berg 

Publication date: 27 May 2020

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.

Full work available at URL: https://arxiv.org/abs/1709.05182

Recommendations

• The complexity of dominating set in geometric intersection graphs
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Domination in Geometric Intersection Graphs
• Parameterized complexity in multiple-interval graphs: domination
• Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy

zbMATH Keywords

dominating setintersection graphW-hierarchy

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Title not available (Why is that?)
• Parametrized complexity theory.
• Computational geometry. Algorithms and applications.
• Fixed-Parameter Tractability and Completeness I: Basic Results
• On the parameterized complexity of multiple-interval graph problems
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• The complexity of dominating set in geometric intersection graphs

Cited In (9)

• The complexity of dominating set in geometric intersection graphs
• Tractabilities and intractabilities on geometric intersection graphs
• New geometric representations and domination problems on tolerance and multitolerance graphs.
• Domination in Geometric Intersection Graphs
• Geometric dominating-set and set-cover via local-search
• The homogeneous broadcast problem in narrow and wide strips. I: Algorithms
• The homogeneous broadcast problem in narrow and wide strips. II: Lower bounds
• A survey on variant domination problems in geometric intersection graphs
• Geometric dominating sets -- a minimum version of the no-three-in-line problem

This page was built for publication: The dominating set problem in geometric intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111873)