Algorithms for intersection graphs of c-intervals and c-pseudodisks

Chandra Chekuri, Tanmay Inamdar

Research output: Contribution to journalArticlepeer-review

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 t2-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 languageEnglish (US)
Article number18
JournalTheory of Computing
Volume18
DOIs
StatePublished - 2022
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Algorithms for intersection graphs of c-intervals and c-pseudodisks'. Together they form a unique fingerprint.

Cite this