## Abstract

Recently it was shown that many classic graph problems—Independent Set, Dominating Set, Hamiltonian Cycle, and more—can be solved in subexponential time on unit-ball graphs. More precisely, these problems can be solved in 2O(n1−1/d) time on unit-ball graphs in Rd , which is tight under ETH. The result can be generalized to intersection graphs of similarly-sized fat objects.

For Independent Set the same running time can be achieved for non-similarly-sized fat objects, and for the weighted version of the problem. We show that such generalizations most likely are not possible for Dominating Set: assuming ETH, we prove that

there is no algorithm with running time 2o(n) for Dominating Set on (non-unit) ball graphs in R3 ;

there is no algorithm with running time 2o(n) for Weighted Dominating Set on unit-ball graphs in R3 ;

there is no algorithm with running time 2o(n) for Dominating Set, Connected Dominating Set, or Steiner Tree on intersections graphs of arbitrary convex (but non-constant-complexity) objects in the plane.

For Independent Set the same running time can be achieved for non-similarly-sized fat objects, and for the weighted version of the problem. We show that such generalizations most likely are not possible for Dominating Set: assuming ETH, we prove that

there is no algorithm with running time 2o(n) for Dominating Set on (non-unit) ball graphs in R3 ;

there is no algorithm with running time 2o(n) for Weighted Dominating Set on unit-ball graphs in R3 ;

there is no algorithm with running time 2o(n) for Dominating Set, Connected Dominating Set, or Steiner Tree on intersections graphs of arbitrary convex (but non-constant-complexity) objects in the plane.

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

Title of host publication | Treewidth, Kernels, and Algorithms |

Editors | F. Fomin, S. Kratsch, E. van Leeuwen |

Pages | 31-48 |

Number of pages | 18 |

ISBN (Electronic) | 978-3-030-42071-0 |

DOIs | |

Publication status | Published - 2020 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 12160 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |