### Samenvatting

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.

Originele taal-2 | Engels |
---|---|

Artikelnummer | 1709.05182 |

Aantal pagina's | 19 |

Tijdschrift | arXiv |

Nummer van het tijdschrift | 1709.05182 |

Status | Gepubliceerd - 2017 |

## Vingerafdruk Duik in de onderzoeksthema's van 'The dominating set problem in geometric intersection graphs'. Samen vormen ze een unieke vingerafdruk.

## Citeer dit

de Berg, M. T., Kisfaludi-Bak, S., & Woeginger, G. (2017). The dominating set problem in geometric intersection graphs.

*arXiv*, (1709.05182), [1709.05182]. https://arxiv.org/abs/1709.05182