## Abstract

Intersection graphs of planar geometric objects such as intervals, disks, rectangles and pseudodisks are well-studied. Motivated by various applications, Butman et al. (ACM Trans. Algorithms, 2010) considered algorithmic questions in intersection graphs of t-intervals. A t-interval is a union of t intervals—these graphs are also referred to as multiple-interval graphs. Subsequent work by Kammer et al. (APPROX-RANDOM 2010) considered intersection graphs of t-disks (union of t disks), and other geometric objects. In this paper we revisit some of these algorithmic questions via more recent developments in computational geometry. For the minimum-weight dominating set problem in t-interval graphs, we obtain a polynomial-time O(t log t)-approximation algorithm, improving upon the previously known polynomial-time t^{2}-approximation by Butman et al. (op. cit.). In the same class of graphs we show that it is NP-hard to obtain a (t − 1 − ϵ)-approximation for any fixed t ≥ 3 and ϵ 0. The approximation ratio for dominating set extends to the intersection graphs of a collection of t-pseudodisks (nicely intersecting t-tuples of closed Jordan domains). We obtain an Ω(1/t)-approximation for the maximum-weight independent set in the intersection graph of t-pseudodisks in polynomial time. Our results are obtained via simple reductions to existing algorithms by appropriately bounding the union complexity of the objects under consideration.

Original language | English (US) |
---|---|

Article number | 18 |

Journal | Theory of Computing |

Volume | 18 |

DOIs | |

State | Published - 2022 |

Externally published | Yes |

## Keywords

- Approximation algorithms
- Computational geometry
- Dominating set
- Geometric set cover
- Independent set
- Multiple interval graphs

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computational Theory and Mathematics