Theory of Computing
-------------------
Title : Algorithms for Intersection Graphs for $t$-Intervals and $t$-Pseudodisks
Authors : Chandra Chekuri and Tanmay Inamdar
Volume : 18
Number : 18
Pages : 1-19
URL : https://theoryofcomputing.org/articles/v018a018
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-\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.