pdf icon
Volume 18 (2022) Article 18 pp. 1-19
Algorithms for Intersection Graphs for $t$-Intervals and $t$-Pseudodisks
Received: December 19, 2019
Revised: June 8, 2022
Published: June 23, 2022
Download article from ToC site:
[PDF (407K)] [PS (1766K)] [Source ZIP]
Keywords: approximation algorithms, multiple interval graphs, geometric set cover, dominating set, independent set
ACM Classification: F.5.2.2, F.6.2
AMS Classification: 68W25

Abstract: [Plain Text Version]

$ \newcommand{\NP}{\mathsf{NP}} $

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-\epsilon)$-approximation for any fixed $t \ge 3$ and $\epsilon > 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 $\Omega(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.