Revised: June 8, 2022

Published: June 23, 2022

**Keywords:**approximation algorithms, multiple interval graphs, geometric set cover, dominating set, independent set

**Categories:**algorithms, approximation algorithms, graphs, interval graphs, indepedent set, set cover, dominating set, geometry, geometric intersection graphs, short

**ACM Classification:**F.5.2.2, F.6.2

**AMS Classification:**68W25

**Abstract:**
[Plain Text Version]

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.