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

Original language | English |
---|---|

Title of host publication | 12th International Symposium on Parameterized and Exact Computation, IPEC 2017 |

Place of Publication | Dagstuhl |

Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |

Pages | 14:1-14:12 |

ISBN (Print) | 978-3-95977-051-4 |

DOIs | |

Publication status | Published - 1 Feb 2018 |

Event | 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) - Vienna, Austria Duration: 6 Sep 2017 → 8 Sep 2017 Conference number: 12 https://algo2017.ac.tuwien.ac.at/ipec |

### Publication series

Name | LIPIcs |
---|---|

Volume | 89 |

### Conference

Conference | 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) |
---|---|

Abbreviated title | IPEC 2017 |

Country/Territory | Austria |

City | Vienna |

Period | 6/09/17 → 8/09/17 |

Internet address |

## Keywords

- Dominating set
- Intersection graph
- W-hierarchy