Authors Chandra Chekuri, Tanmay Inamdar,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19
www.theoryofcomputing.org
Algorithms for Intersection Graphs of
๐ก-Intervals and ๐ก-Pseudodisks
Chandra Chekuriโ Tanmay Inamdarโ
Received December 19, 2019; Revised June 8, 2022; Published June 23, 2022
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 ๐ก-intervals. A ๐ก-interval is a union of ๐ก intervalsโthese
graphs are also referred to as multiple-interval graphs. Subsequent work by Kammer
et al. (APPROX-RANDOM 2010) considered intersection graphs of ๐ก-disks (union
of ๐ก 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 ๐ก-interval graphs, we obtain a
polynomial-time ๐(๐ก log ๐ก)-approximation algorithm, improving upon the previously
known polynomial-time ๐ก 2 -approximation by Butman et al. (op. cit.). In the same
class of graphs we show that it is NP-hard to obtain a (๐ก โ 1 โ ๐)-approximation for
any fixed ๐ก โฅ 3 and ๐ > 0.
The approximation ratio for dominating set extends to the intersection graphs of
a collection of ๐ก-pseudodisks (nicely intersecting ๐ก-tuples of closed Jordan domains).
We obtain an ฮฉ(1/๐ก)-approximation for the maximum-weight independent set in the
โ Chandra Chekuri is supported in part by NSF grants CCF-1526799 and CCF-1910149.
โ Tanmay Inamdar is supported in part by NSF grant CCF-1615845.
ACM Classification: F.5.2.2, F.6.2
AMS Classification: 68W25
Key words and phrases: approximation algorithms, computational geometry, multiple interval
graphs, geometric set cover, dominating set, independent set
ยฉ 2022 Chandra Chekuri and Tanmay Inamdar
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2022.v018a018
C HANDRA C HEKURI AND TANMAY I NAMDAR
intersection graph of ๐ก-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.
1 Introduction
A number of interesting optimization problems can be modeled as packing and covering
problems involving geometric objects in the plane such as intervals, disks, rectangles, triangles,
convex polygons and pseudodisks1. Some of these problems can be studied via properties
of the intersection graph2 defined by the objects under consideration. Geometric intersection
graphs are interesting for both theoretical and practical reasons. For instance, the well-known
KoebeโAndreevโThurston theorem shows that every planar graph can be represented as the
intersection graph of interior-disjoint disks in the plane (see Sections 13.6 and 13.7 of [34]).
Interval graphs are another well-studied class of geometric intersection graphs that are
defined by a finite set of intervals on the real line. Algorithmic problems on interval graphs have
been motivated by applications in scheduling, resource allocation, and computational biology.
Several papers [8, 9, 10, 26] have studied geometric intersection graphs in the setting where
each composite object is now the union of a set of base geometric objects. To make the discussion
concrete we first discuss ๐ก-interval graphs. For an integer parameter ๐ก โฅ 1, a ๐ก-interval is the
union of ๐ก intervals. A ๐ก-interval graph is the intersection graph of a set of ๐ก-intervals. These
graphs are also called multiple-interval graphs. They have been well-studied from graph
theoretic and algorithmic points of view. For instance, every graph with maximum degree ฮ can
be represented as a ๐ก-interval graph for ๐ก = d(ฮ + 1)/2e [21]. This demonstrates the modeling
power obtained by considering unions of simple geometric objects. Butman et al. [10], building
on [8, 9] (which primarily studied the maximum independent set problem), considered several
optimization problems in ๐ก-interval graphs such as minimum vertex cover, dominating set
and maximum clique. Unlike the case of interval graphs, where these problems are tractable,
the corresponding problems in ๐ก-interval graphs are NP-hard even for small values of ๐ก and
unweighted instances; this can be seen from the preceding comment on the modeling power
of ๐ก-interval graphs, and the NP-hardness of several problems on bounded-degree graphs.
Butman et al. describe polynomial-time approximation algorithms for these problems, and the
approximation ratios they obtain depend on ๐ก. We refer the reader to [10] and references therein
for a more detailed discussion on applications of multiple-interval graphs. In subsequent work,
Kammer et al. [26, 25] studied (among other models) intersection graphs of ๐ก-disks (a ๐ก-disk is a
union of ๐ก disks) and ๐ก-fat objects3. They obtained approximation algorithms for optimization
problems on these graphs such as maximum independent set, minimum vertex cover and
1A collection of pseudodisks is a set of closed Jordan domains in which the boundaries of any two in the set intersect
in at most two points, counting a point of tangency as a double intersection. Note that the property is defined by the
entire set. See also Def. 2.4.
2The intersection graph of a set of sets has a node for each set and two nodes are adjacent if the corresponding
sets intersect (their intersection is not empty).
3There are several equivalent definitions of fatness in the plane. We say that a geometric object ๐ is ๐ผ-fat for some
๐ผ โฅ 1, if the ratio of the radius of the smallest enclosing disk of ๐ to the radius of the largest disk enclosed by ๐, is at
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 2
A LGORITHMS FOR I NTERSECTION G RAPHS OF ๐ก-I NTERVALS AND ๐ก-P SEUDODISKS
minimum dominating set. We also refer the reader to [38] for connections between geometric
intersection graphs and approximation algorithms.
We now formally define the three problems that are central to this paper. Let ๐บ = (๐ , ๐ธ)
be an undirected graph with non-negative rational weights on the nodes. ๐ โ ๐ is said to be
a dominating set if for any node ๐ข โ ๐, ๐ข โ ๐ or ๐ข has a neighbor in ๐. The Minimum-Weight
Dominating Set (MWDS) problem is to find a dominating set of minimum weight in a given
weighted graph. A subset of nodes, ๐ผ โ ๐, is said to be an independent set if no two nodes in ๐ผ are
adjacent in ๐บ. The Maximum-Weight Independent Set (MWIS) problem is to find an independent
set of maximum weight in a given weighted graph. Consider a set system (๐ , ๐ฎ), where ๐ is a
finite ground set, and ๐ฎ is a set of subsets of ๐. Each set in ๐ฎ has a non-negative rational weight.
The Minimum-Weight Set Cover (MWSC) problem is to find a set โ โ โ ๐ฎ of minimum weight
such that ๐ = ๐๐ โ๐ฎ ๐ ๐ . We denote the unweighted versions (that is, all weights are unit) of the
ร
MWDS, MWIS, and MWSC problems by MDS, MIS, and MSC, respectively.
Convention 1.1 (rational weights). In all our results, the weights are rational numbers.
Remark 1.2. The focus in this paper is on polynomial-time approximation algorithms for
a class of NP-hard optimization problems. As common in this literature, we use the term
โapproximation algorithmโ to refer to a deterministic polynomial-time approximation algorithm unless
we explicitly mention the running time or additional aspects such as the use of randomness or
specific oracles.
Our assumption that the weights are rational (as opposed to real) is necessitated by the fact
that our algorithms rely on solving linear programming relaxations. The emphasis in this paper
is on the approximation ratio achievable via the LP relaxation approach. For these reasons we
do not emphasize the precise polynomial running times of the algorithms.
1.1 Motivation and our contribution
In this paper we utilize powerful techniques from computational geometry [11, 12, 35] to
provide algorithmic results for ๐ก-interval graphs, ๐ก-disks and other geometric objects, in a unified
fashion. For some problems we obtain substantially improved approximation bounds that
are near-optimal. Our results extend to ๐ก-pseudodisks while techniques in earlier work that
exploited properties of intervals [10], or fatness properties of the underlying objects [26], do not
apply.
Before stating our results in full generality, we discuss the following geometric covering
problem to illustrate some of the basic ideas. Given a set of points on the line, and a set of
weighted intervals, find a minimum-weight subset of the given intervals that cover all the points.
This is a special case of MWSC, and can be solved efficiently via dynamic programming or via
mathematical programming. The natural LP relaxation in the interval case happens to yield
an integer polytopeโthe incidence matrix between intervals and points is totally unimodular
(TUM) (it has the consecutive ones property) [33]. Now consider the same problem where
we need to cover a given set of points by (weighted) ๐ก-intervals. Approximation algorithms
most ๐ผ. We say that โ is a set of fat objects, if there exists a constant ๐ผ such that every object in โ is ๐ผ-fat.
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 3
C HANDRA C HEKURI AND TANMAY I NAMDAR
for this problem were first given by Hochbaum and Levin [23] (in the more general setting of
multicover)โthey derived a ๐ก-approximation for this problem by reducing it, via the natural LP
relaxation, to the case of ๐ก = 1. As far as we are aware, this was the best known approximation
to this problem until our work. A natural question is whether the approximation ratio of ๐ก can
be improved. In this paper we show that an ๐(log ๐ก)-approximation can be obtained via tools
from computational geometry such as shallow-cell complexity and quasi-uniform sampling.
It is an easy observation that an MWSC instance in which each set has at most ๐ก elements can
be captured as a special case of covering points by ๐ก-intervals. Thus, for large values of ๐ก, via
known hardness results for MSC [30, 18], one obtains NP-hardness of (๐ log ๐ก)-approximation
for some universal constant ๐ > 0 for covering points by ๐ก-intervals. The geometric machinery
allows us to derive an ๐(log ๐ก)-approximation in the much more general setting of covering
points by ๐ก-pseudodisks.
We state our results for ๐ก-pseudodisks which capture several shapes of interest, including
intervals and disks. The geometric approach applies in greater generality but here we confine
our attention to pseudodisks.
โข An ๐(log ๐ก)-approximation for minimum-weight cover of points by ๐ก-pseudodisks, in
other words, the instances of MWSC defined by points and ๐ก-pseudodisks in the plane
(Theorem 3.9).
โข An ๐(๐ก log ๐ก)-approximation for MWDS in ๐ก-pseudodisk graphs (Theorem 3.7). Even
for ๐ก-intervals, the best known previous approximation factor was ๐ก 2 [10]. We observe
that, via a simple reduction from Hypergraph Vertex Cover, it is NP-hard to approximate
MDS within a factor better than (๐ก โ 1 โ ๐) for any fixed ๐ > 0 in ๐ก-interval graphs. We
also show UG-hardness4 for reaching the slightly improved approximation ratio of (๐ก โ ๐)
(Corollary 3.13).
โข An ฮฉ(1/๐ก)-approximation for MWIS in ๐ก-pseudodisk graphs (Theorem 4.4). A 1/(2๐ก)-
approximation has been known for ๐ก-intervals [9]. For more general shapes such as
disks and fat objects, the approximation bounds in [25] depend on ๐ก and on the fatness
parameters. (See [25] for the actual definition.) Our approach also works for packing
weighted ๐ก-pseudodisks into capacitated points (Theorem 4.5).
Our results are obtained via simple reductions to existing algorithms in geometric packing
and covering, however, the known algorithms use fairly sophisticated ideas. Consequently, in
some cases, the constants in the approximation guarantees we obtain may be worse compared
to the known results for special cases. On the other hand, our results are applicable to a much
more general class of geometric objects. It may be possible to improve the constants for various
special cases by examining the details more closely.
We describe the necessary geometric background in the next subsection.
4 UG refers to Khotโs โUnique Gamesโ problem [28, 29].
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 4
A LGORITHMS FOR I NTERSECTION G RAPHS OF ๐ก-I NTERVALS AND ๐ก-P SEUDODISKS
1.2 Background from geometric approximation via LP relaxations
The approximability of MWDS and MWIS in general graphs is well understood and essentially
tight upper and lower bounds are known. For MWDS there is an approximation ratio of
(1 + ln ๐) where ๐ is the number of nodes [36, 37], and moreover, it is NP-hard to obtain an
((1 โ ๐(1)) ln ๐)-approximation [30, 18] even in the unweighted setting. In general graphs, it is
NP-hard to approximate MIS to within a factor of 1/๐ 1โ๐ for any fixed ๐ > 0 [22, 39], and the
best known approximation ratio is ฮฉ((log๐ ๐)/๐) for some small integer constant ๐ (see [19, 6]).
MWDS and MWSC are closely related and their approximability is essentially the same.
The preceding results rule out constant-factor approximations for MWDS and MWIS in
graphs, even in the unweighted case. However, in various geometric settings it is possible
to obtain substantially improved algorithms including approximation schemes (PTASes and
QPTASes) [12, 20, 11, 2, 32, 1] and constant-factor approximations [12, 11, 20]. In this paper we
are interested in LP-based approximations for MWSC and MWIS that have been established
via techniques relying on the union complexity of the underlying geometric objects. Union
complexity measures the worst-case representation size of the union of a given set of objects of
a particular type or shape. In the setting of planar objects, the typical measure is the number of
vertices in the arrangement that appear on the boundary of the union. It is well known that
many geometric objects such as intervals (on a line), disks, and squares (in the plane) have linear
union complexity. In fact, this holds for an even larger class of sets of geometric objects, namely
collections of pseudodisks [3, 27].
Bounds on union complexity have been used to obtain constant-factor and sublogarithmic
approximations for geometric MWSC and its variants (see [15, 13, 35, 11], and [31] for a survey).
Chan and Har-Peled [12] showed that upper bounds on union complexity can also be used to
obtain improved approximations for the MWIS problem. They give an LP rounding algorithm
with approximation guarantee ฮฉ(๐/๐ข(๐)) for computing an MWIS of ๐ objects where ๐ข(๐) is an
upper bound on the worst-case union complexity of ๐ objects under consideration. We use this
result to give an ฮฉ(1/๐ก)-approximation for computing MWIS of ๐ก-pseudodisks. This implies
ฮฉ(1/๐ก)-approximation for MWIS of ๐ก-intervals, ๐ก-disks and ๐ก-squares; however, these results
have already been known [8, 26] but these previous results are based on using certain โfatnessโ
properties of the underlying geometric objects, and hence do not apply to arbitrary pseudodisks.
Shallow-cell complexity (SCC) of a set system provides quantitative bounds on a certain hereditary
sparsity property [11]. A formal definion is given later in the paper. Upper bounds on SCC
have been used to obtain improved approximations for MWSC and MWDS in geometric settings
as well as some combinatorial settings. The general approach here is to round a feasible LP
solution using a framework called quasi-uniform sampling introduced by Varadarajan [35] for
geometric settings. This framework was refined and improved by Chan et al. [11]. We use this
framework, and some known results on SCC for disks and pseudodisks [20, 5], to derive our
results for MWDS and MWSC on ๐ก-pseudodisks.
Organization. Section 2 introduces some relevant notation and definitions. Section 3 describes
algorithms for covering problems MWDS and MWSC. Section 4 describes algorithms for MWIS
and a generalization.
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 5
C HANDRA C HEKURI AND TANMAY I NAMDAR
D C D C
A A
B B
Figure 1: Left: ๐ฎ 0 = {๐ด, ๐ต, ๐ถ, ๐ท} is a set of closed Jordan domains that intersect nicely, and
hence is a collection of pseudodisks. Right: ๐ฎ = {๐ด โช ๐ถ, ๐ต โช ๐ท} is a collection of 2-pseudodisks.
2 Preliminaries
Let ๐ be a family of sets we call โbasic objects.โ Given ๐, a ๐ก-object is defined as the union of
at most ๐ก basic objects, where ๐ก is a positive integer. We do not assume that the ๐ก basic objects
that define a specific ๐ก-object are pairwise non-intersecting; such an assumption may be helpful
in some settings but can be restrictive in others. Without loss of generality, we assume that
each ๐ก-object is a union of exactly ๐ก basic objects. We are typically interested in the case when
the basic objects come from a specific class of geometric shapes such as intervals, disks, and
pseudodisks (closed Jordan domains).
Definition 2.1 (closed Jordan domain). A subset of the plane is a closed Jordan domain if it is a
compact subset of โ2 whose boundary is a simple closed curve.
Definition 2.2 (nice intersection). We say that two closed Jordan domains intersect nicely if their
boundaries are either (i) disjoint or (ii) properly intersect exactly twice or (iii) are tangent exactly
once.
Definition 2.3 (๐ก-pseudodisk). For ๐ก โฅ 1, a ๐ก-pseudodisk is the union of at most ๐ก closed Jordan
domains that pairwise intersect nicely.
Definition 2.4 (collection of pseudodisks and ๐ก-pseudodisks). Let ๐ฎ 0 be a set of closed Jordan
domains in the plane. We call ๐ฎ 0 a collection of pseudodisks [5] if the boundaries of any two
distinct pseudodisks in ๐ฎ 0 intersect nicely. Let ๐ฎ 0 be a collection of pseudodisks, and let ๐ฎ be a
set of objects where each object in ๐ฎ is the union of at most ๐ก objects from ๐ฎ 0. We say that ๐ฎ is a
collection of ๐ก-pseudodisks.
Remark 2.5. When speaking of a collection ๐ฎ of ๐ก-pseudodisks, we understand that there is an
underlying collection ๐ฎ 0 of pseudodisks.
The definition allows two different ๐ก-pseudodisks in ๐ฎ to share a common pseudodisk from
๐ฎ 0.
(1) (2) (๐ก)
Consider a ๐ก-object ๐ ๐ . We use ๐ ๐ , ๐ ๐ , . . . , ๐ ๐ to denote the objects whose union equals
(1) (2) (๐ก)
๐ ๐ . Slightly abusing the notation, we also denote by ๐ ๐ the set {๐ ๐ , ๐ ๐ , . . . , ๐ ๐ }. Next, we
formally define the notion of union complexity.
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 6
A LGORITHMS FOR I NTERSECTION G RAPHS OF ๐ก-I NTERVALS AND ๐ก-P SEUDODISKS
D C
A B
Figure 2: The vertices, elementary arcs, and faces of dimension two formed by the collection
๐ฎ 0 = {๐ด, ๐ต, ๐ถ, ๐ท} of pseudodisks are shown as points (filled squares/circles), arcs, and solid
regions, respectively. For โ 0 = {๐ด, ๐ถ, ๐ท} the vertices appearing on ๐ฐ(โ 0) are shown as blue
squares.
2.1 Union complexity
The following definitions are adapted from [3, pp. 13-14]. Let ๐ฎ 0 be a collection of pseudodisks.
Let ๐ฐ(๐ฎ 0) = ๐โ๐ฎ0 ๐ denote their union and let ๐๐ฐ(๐ฎ 0) denote the boundary of the union.
ร
Each face of ๐๐ฐ(๐ฎ 0) is a maximal connected (relatively open) subset of ๐๐ฐ(๐ฎ 0) that lies on the
boundaries of a fixed subset โ 0 โ ๐ฎ 0, and avoids all other pseudodisks in in ๐ฎ 0. The faces of
dimension 0 and 1 are called vertices and elementary arcs, respectively. We say that ๐ฎ 0 has union
complexity ๐ข(ยท) for a function ๐ข : โค+ โ โค+ if the following condition is true: for any subset
โ 0 โ ๐ฎ 0, the number of vertices on ๐๐ฐ(โ 0) is at most ๐ข(|โ 0 |).
In the rest of the paper we assume that ๐ข(๐) โฅ ๐ for any ๐ โฅ 1 and that ๐ข is non-decreasing.
These are natural assumptions for the settings we consider.
For example, a set of disksโand more generally, a collection of pseudodisksโin the plane
have linear union complexity [3, 27]. The union complexity of ๐ fat triangles is ๐(๐ logโ ๐) [4].
The union complexity of ๐ axis-aligned rectangles in the plane can be ฮฉ(๐ 2 ).
3 Minimum-Weight Dominating Set and Set Cover
As in Butman et al. [10], we consider the following slight generalization of the MWDS that is
called the Red-Blue Dominating Set Problem. The input is an undirected bipartite intersection
graph ๐บ = (โ t โฌ, ๐ธ), where โ = {๐
1 , . . . , ๐
๐ } and โฌ = {๐ต1 , . . . , ๐ต ๐ } are sets of red and blue
๐ก-objects, respectively. There is an edge between ๐
๐ โ โ and ๐ต ๐ โ โฌ if ๐
๐ โฉ ๐ต ๐ โ โ
. Since
each node corresponds to a (red or blue) ๐ก-object, we will use the term โnodeโ and โ๐ก-objectโ
interchangeably. Each ๐
๐ โ โ has a non-negative weight ๐ค ๐ . The goal is to find a subset โ 0 โ โ
of minimum weight such that every blue node ๐ต ๐ has a neighbor in the set โ 0. Note that the
standard MWDS problem is equivalent to the setting where โ = โฌ.
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 7
C HANDRA C HEKURI AND TANMAY I NAMDAR
3.1 LP relaxation and rounding
Let โ = (โ, โฌ) denote the given instance of the (generalized) MWDS. In an integer programming
formulation we have a {0, 1} variable ๐ฅ ๐ corresponding to a red ๐ก-object ๐
๐ which is intended
to be assigned 1 if ๐
๐ is selected in the solution, and is assigned 0 otherwise. We relax the
integrality constraints and describe the natural LP relaxation below.
ร
minimize ๐ค๐ ๐ฅ๐
๐
๐ โโ
ร
subject to ๐ฅ ๐ โฅ 1, โ๐ต ๐ โ โฌ (3.1)
๐
๐ :๐ต ๐ โฉ๐
๐ โ โ
๐ฅ ๐ โ [0, 1], โ๐
๐ โ โ (3.2)
The LP-relaxation can be solved in polynomial time assuming that we are given the
intersection graph defined by โ. Let ๐ฅ be an optimal LP solution ร for the given instance
โ = (โ, โฌ). Since ๐ฅ is feasible, for every blue ๐ก-object ๐ต ๐ , we have ๐ฅ ๐ โฅ 1. For each
๐
๐ :๐ต ๐ โฉ๐
๐ โ โ
ร
๐ต ๐ โ โฌ, let ๐ 0๐ denote an object maximizing the quantity ๐ฅ ๐ , where the ties are broken
๐
๐ :๐ 0๐ โฉ๐
๐ โ โ
arbitrarily. Let โฌ 0 B {๐ 0๐ : ๐ต ๐ โ โฌ}. We emphasize that โฌ 0 is a set of (1-)objects, whereas โ is a
ร
set of ๐ก-objects. Note that for any ๐ 0๐ โ โฌ 0, ๐ฅ ๐ โฅ 1/๐ก.
๐
๐ :๐ 0๐ โฉ๐
๐ โ โ
๐
๐ โ โ, let ๐ฅ 0๐ = min{๐ก๐ฅ ๐ , 1}, and let ๐ฅ 0 denote the resulting solution. Then, for any
For anyร
๐ 0๐ โ โฌ 0, ๐ฅ 0๐ โฅ 1. The following observation follows from the definition of ๐ฅ 0.
๐
๐ :๐ 0๐ โฉ๐
๐ โ โ
Observation 3.1. The solution ๐ฅ 0 is feasible for the instance โ 0 = (โ, โฌ 0), and we have that ๐
๐ โโ ๐ค ๐ ๐ฅ ๐ โค
0
ร
๐ก ยท ๐
๐ โโ ๐ค ๐ ๐ฅ ๐ .
ร
The preceding step to reduce to โ 0 is essentially the same as in [10].
3.1.1 Shallow-cell complexity
Definition 3.2 (Shallow-cell complexity). Let ๐ด โ {0, 1} ๐ร๐ denote an ๐ ร ๐ (0, 1)-matrix. Let
1 โค ๐ โค ๐ โค ๐. Let ๐ be any set of ๐ columns and let ๐ด๐ be the matrix restricted to the columns
of ๐. If the number of distinct rows in ๐ด๐ with at most ๐ ones is bounded by ๐ (๐, ๐) for any
choice of ๐, ๐ and ๐, then ๐ด is said to have the shallow-cell complexity ๐ (๐, ๐).
Now, we describe how to round ๐ฅ 0 to an integral solution via quasi-uniform sampling
technique. The standard LP relaxation for an MWSC instance (๐ , ๐ฎ 0) is as follows.
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 8
A LGORITHMS FOR I NTERSECTION G RAPHS OF ๐ก-I NTERVALS AND ๐ก-P SEUDODISKS
ร
minimize ๐ค๐ ๐ฅ๐
๐ ๐ โ๐ฎ 0
ร
subject to ๐ฅ ๐ โฅ 1, โ๐ โ ๐ (3.3)
๐ ๐ 3๐
๐ฅ ๐ โ [0, 1], โ๐ ๐ โ ๐ฎ 0 (3.4)
Let ๐ด โ {0, 1} ๐ร๐ denote the constraint matrix in the LP relaxation above. This is the
incidence matrix of the set system {๐ ๐ | 1 โค ๐ โค ๐ } : each row of ๐ด corresponds to an element,
and each column corresponds to a set. The entry ๐ด ๐๐ = 1 if the element ๐ is contained in ๐ ๐ ,
otherwise ๐ด ๐๐ = 0.
The following crucial definition is from [11].
Definition 3.3 (Shallow-cell complexity of MWSC instance). Let ๐ด be the constraint matrix
of the MWSC instance โ. We define the shallow-cell complexity of โ to be the shallow-cell
complexity of ๐ด.
Using bounds on the shallow-cell complexity of an MWSC instance, it is possible to round a
feasible LP solution using a technique known as quasi-uniform sampling [11, 35].
Theorem 3.4 (Chan et al. [11], Varadarajan [35]). Consider an MWSC instance with shallow-cell
complexity ๐ (๐, ๐) = ๐๐(๐) ยท ๐ ๐ , where ๐(๐) = ๐(๐), and ๐ โฅ 0 is a constant. Then, there exists a
polynomial-time algorithm to round a given fractional solution to the LP relaxation for this instance to
an integral solution whose cost is within an ๐(max{log ๐(๐), 1}) factor of the cost of the fractional
solution, where the constant hidden in the big-Oh notation depends on the exponent ๐, and ๐ is the
number of sets in the given instance.
Usually, ๐(๐) is a function of ๐ such that ๐(๐) = ๐(๐). However, the same guarantee holds
even when ๐ is independent of ๐ . When we apply this theorem, we will set ๐(๐) = ๐(๐ก 4 ),
which is independent of ๐.
Now, we consider an instance โ 0 = (โ, โฌ 0) of the MWDS problem obtained in the previous
(๐)
section. Recall that โ is a set of ๐ก-objects and โฌ is a set of 1-objects. Now, let โ 0 = {๐ ๐ โ ๐
๐ :
๐
๐ โ โ} denote the set of constituent red 1-objects from โ. Let โ 00 = (โ 0 , โฌ 0) denote the MWDS
instance thus obtained. Notice that an MWDS instance can also be thought of as an MWSC
instance. We first prove the following simple lemma.
Lemma 3.5. Let โ 0 , โ 00 be MWDS instances as defined above. If the shallow-cell complexity of โ 00 is
๐ (๐, ๐), then the shallow-cell complexity of the corresponding instance โ 0 is ๐(๐, ๐) โค ๐ (๐๐ก, ๐๐ก) for any
1 โค ๐ โค ๐ โค ๐.
0
Proof. We prove this fact from the definition of the shallow-cell complexity. Let ๐ดโ denote
the constraint matrix corresponding to the instance โ 0. Fix some positive integers ๐, ๐ such
0
that 1 โค ๐ โค ๐ โค |โ|, and fix a set ๐ โ โ of columns (i. e., ๐ก-objects), where |๐| = ๐. Let ๐ดโ๐
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 9
C HANDRA C HEKURI AND TANMAY I NAMDAR
denote the constraint matrix restricted to the columns corresponding to ๐. Let ๐ denote the set
0
of distinct rows (i. e., blue objects) in ๐ดโ๐ with at most ๐ ones. We seek to bound |๐|.
(๐)
Let ๐0 = {๐ ๐ โ ๐
๐ : ๐
๐ โ ๐} be the corresponding constituent 1-objects. Note that ๐0 โ โ 0,
00
and |๐0 | โค ๐๐ก. Let ๐ดโ denote the constraint matrix corresponding to the instance โ 00 and let
00 00 00
๐ดโ๐0 denote ๐ดโ restricted to the columns of ๐0. Let ๐ 0 denote the set of rows in ๐ดโ๐0 with at
0
most ๐๐ก ones. Note that, if a row has at most ๐ ones in ๐ดโ๐ , then it corresponds to exactly one
row in ๐ 0. Therefore, |๐| โค |๐ 0 | โค ๐ (๐๐ก, ๐๐ก), where the last inequality follows from the definition
of the shallow-cell complexity of the instance โ 00.
Now, we state the known bounds on the shallow-cell complexity of an MWDS instance
defined by red and blue sets of pseudodisks.
Theorem 3.6 (Aronov et al. [5]). The shallow-cell complexity of an MWDS instance defined by a
collection of pseudodisks is at most ๐ (๐, ๐) = ๐(๐ ๐ 3 ).
Combining Theorem 3.4, Theorem 3.6, and Lemma 3.5, we obtain the following result.
Theorem 3.7. There exists a polynomial-time ๐(๐ก log ๐ก)-approximation algorithm for the Red-Blue
Dominating Set problem defined by a collection of ๐ก-pseudodisks.
Proof. Let โ = (โ, โฌ) be the original instance and let ๐ฅ be an optimal LP solution. Define
instance โ 0 = (โ, โฌ 0) and the corresponding LP solution ๐ฅ 0 as before. From Observation 3.1,
we have that ๐
๐ โโ ๐ค ๐ ๐ฅ 0๐ โค ๐ก ยท ๐
๐ โโ ๐ค ๐ ๐ฅ ๐ . By Lemma 3.5 the shallow-cell complexity of โ 0 is
ร ร
๐(๐, ๐) โค ๐ (๐๐ก, ๐๐ก), where ๐ (๐, ๐) = ๐(๐ ๐ 3 ) by Theorem 3.6. Therefore, ๐(๐, ๐) โค ๐(๐๐ก 4 ๐ 3 ).
Now, using the algorithm from Theorem 3.4 with ๐(๐) = ๐(๐ก 4 ), we can round ๐ฅ 0 to an integral
solution of cost at most ๐(log ๐ก) ยท ๐
๐ โโ ๐ค ๐ ๐ฅ 0๐ โค ๐(๐ก log ๐ก) ยท ๐
๐ โโ ๐ค ๐ ๐ฅ ๐ , where the inequality
ร ร
follows from Observation 3.1.
Remark 3.8. Suppose we have an instance of (โ, โฌ) of generalized MWDS where each red object
is a ๐ก ๐
-pseudodisk and each blue object is a ๐ก ๐ต -pseudodisk. Then the preceding analysis can be
extended to obtain an ๐(๐ก ๐ต log ๐ก ๐
)-approximation. We note that for the analogous version of
intervals, a (๐ก ๐ต ยท ๐ก ๐
)-approximation was obtained in [10].
3.1.2 Geometric MWSC with ๐ก-objects.
Let ๐ฎ 0 denote a set of (1-)objects. Consider a Geometric MWSC instance (๐ , ๐ฎ), where ๐ is
a set of points, and ๐ฎ is a set of ๐ sets, each of which is obtained by taking the union of at
most ๐ก (1-)objects from ๐ฎ 0. Each set in ๐ฎ has a non-negative weight. The goal is to find a
minimum-weight set โ โ ๐ฎ that covers the set of points ๐. Furthermore, suppose the set system
(๐ , ๐ฎ 0) has shallow-cell complexity ๐ (๐, ๐) = ๐ ๐ ๐ , for some fixed constant ๐. This includes
geometric objects such as intervals on a line and (pseudo-)disks in the plane. Then, using similar
arguments as we did for MWDS, one can obtain a bound of ๐(๐ ๐ ๐ ๐ก ๐+1 ) on the shallow-cell
complexity of the MWSC instance (๐ , ๐ฎ). Then Theorem 3.4 implies an ๐(log ๐ก)-approximation
for the MWSC instance (๐ , ๐ฎ).
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 10
A LGORITHMS FOR I NTERSECTION G RAPHS OF ๐ก-I NTERVALS AND ๐ก-P SEUDODISKS
When ๐ฎ 0 is a set of fat triangles, the shallow-cell complexity of the system (๐ , ๐ฎ 0) can
be bounded by ๐ (๐, ๐) = ๐ logโ ๐ ยท ๐ ๐ , for some fixed constant ๐ [4, 11]. We can then bound
the shallow-cell complexity of the MWSC instance (๐ , ๐ฎ) by ๐ (๐๐ก, ๐๐ก) = ๐ logโ (๐๐ก) ยท ๐ก ๐+1 ๐ ๐ .
Then, Theorem 3.4 implies an ๐(log(๐ก ๐+1 ยท logโ (๐๐ก))) = ๐(log ๐ก + log logโ (๐))-approximation.
Therefore, we obtain the following result.
Theorem 3.9. There is a polynomial-time ๐(log ๐ก)-approximation algorithm for MWSC instances
defined by covering points by ๐ก-pseudodisks. For covering points by ๐ก-fat-triangles, there is an ๐(log ๐ก +
log logโ (๐))-approximation where ๐ is the number of triangles in the instance.
The preceding result improves the ๐ก-approximation for covering points by ๐ก-intervals [23].
The approximation ratio of ๐(log ๐ก) is tight up to constant factors; it is NP-hard to obtain an
๐(log ๐ก)-approximation for covering points by ๐ก-intervals. This follows via a reduction from
MWSC [10].
3.2 Integrality of MWDS LP for intervals
Let โ = (โ, โฌ) be an MWDS instance where โ and โฌ are set of intervals on a line. In this
subsection, we prove that the MWDS LP for intervals is integral. Butman et al. [10] proved this
fact using a primal-dual algorithm that constructs an integral solution of the same cost as the LP.
Here we give a simpler proof via the structure of the constraint matrix.
First, we preprocess blue intervals such that no blue interval is completely contained inside
another blue interval. To understand this, suppose ๐ต1 , ๐ต2 โ โฌ are two intervals such that
๐ต1 โ ๐ต2 . Then, any feasible integral solution must include a red interval ๐
that intersects ๐ต1 ,
and thus ๐ต2 . Furthermore, the LP constraint corresponding to ๐ต2 is implied by the constraint
corresponding to ๐ต1 . Therefore, the feasible regions of the LPโs corresponding to โ and the
instance obtained by removing ๐ต2 are the same. This justifies removing ๐ต2 from โ. Repeating
this removal step as along as one blue interval is contained in another blue interval, we obtain
an instance โ 0.
In the following theorem we show that the constraint matrix of the LP corresponding to โ 0
satisfies the consecutive ones property, and thus it is totally unimodular. This implies that the
LP corresponding to โ 0 (and therefore โ) is integral (see, e.g., [33]).
Theorem 3.10. Let โ = (โ, โฌ) be an MWDS instance, where โ and โฌ are sets of (1-)intervals. Then,
the MWDS LP is integral.
Proof. Let us denote the left (resp. right) endpoint of an interval ๐ผ by Left(๐ผ) (resp. Right(๐ผ)). Let
๐ด denote the constraint matrix corresponding to the preprocessed instance, where the rows
(i. e., blue intervals) are sorted in the non-decreasing order of their left endpoints. We show that
๐ด has the consecutive ones property for any column.
Consider any column (i. e., a red interval) ๐
. Let ๐ต ๐ and ๐ต ๐ denote the first (leftmost) and
last (rightmost) blue intervals intersecting ๐
in this order respectively. Note that ๐ โค ๐. Now,
suppose for contradiction that there is an interval ๐ตโ with ๐ < โ < ๐ that does not intersect ๐
.
Let us consider two cases.
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 11
C HANDRA C HEKURI AND TANMAY I NAMDAR
If Right(๐ตโ ) < Left(๐
), then we have that Left(๐ต ๐ ) < Left(๐ตโ ) โค Right(๐ตโ ) < Left(๐
) โค Right(๐ต ๐ ).
Here, the third and fourth inequalities follow from the assumptions that ๐
โฉ ๐ตโ = โ
and
๐
โฉ ๐ต ๐ โ โ
respectively. However, this implies that ๐ตโ โ ๐ต ๐ , which is a contradiction.
On the other hand, if Right(๐ตโ ) > Left(๐
), then it must be the case that Left(๐ตโ ) > Right(๐
);
otherwise ๐
โฉ ๐ตโ โ โ
, which is a contradiction. However, this implies that Left(๐
) โค Right(๐
) <
Left(๐ตโ ) โค Left(๐ต ๐ ) โค Right(๐ต ๐ ), where the third inequality follows from the fact that โ < ๐.
However, this contradicts the assumption that ๐ต ๐ โฉ ๐
โ โ
.
Thus, the column corresponding to ๐
satisfies the consecutive ones property.
3.3 Hardness results for MWDS
We show hardness of approximation for MWDS in ๐ก-interval graphs via a simple reduction. We
first consider the Red-Blue Dominating Set problem for ๐ก-intervals which illustrates the basic
idea. We then modify it slightly to prove hardness for the MWDS problem.
Let (๐ , ๐ฎ) be an ๐ -uniform instance of MWSC. That is, any element in ๐ is contained in
exactly ๐ sets of ๐ฎ. We reduce this to the Red-Blue Dominating Set problem as follows. For every
set ๐ ๐ โ ๐ฎ, we add a red interval ๐
๐ = [๐ฆ ๐ , ๐ง ๐ ] on the line. The red intervals are non-overlapping;
concretely, it suffices to choose ๐ฆ ๐ = 2๐ and ๐ง ๐ = 2๐ + 1 for each ๐. We set the weight of ๐
๐ to be
that of ๐ ๐ . For any element ๐ ๐ โ ๐, we add a exactly ๐ blue points coinciding with points ๐ง ๐ ,
where ๐ ๐ โ ๐ ๐ . Note that a blue ๐ -point is covered iff we select a red interval that covers one of
its constituent ๐ points. Thus, there is a one-to-one correspondence between feasible solutions
to the original MWSC instance, and feasible solutions to the Red-Blue dominating set instance
that is created. The following hardness results are known for the ๐ -uniform MWSC problem
even when sets have unit weights.
Theorem 3.11.
1. It is NP-hard to obtain a ( ๐ โ 1 โ ๐)-approximation for ๐ -uniform Set Cover, for any fixed ๐ โฅ 3
and ๐ > 0 (Dinur et al. [16]).
2. Furthermore, it is UG-hard to obtain an ( ๐ โ ๐)-approximation for any fixed ๐ โฅ 2 and ๐ > 0
(Khot and Regev [29]).
Therefore, from the preceding reduction, we get the following hardness results for the
Red-Blue Dominating Set problem, even when all weights are unit.
Theorem 3.12. It is NP-hard to obtain a (๐ก โ 1 โ ๐)-approximation for the special case of Red-Blue
Dominating Set problem where โ is a set of intervals and โฌ is a set of ๐ก-points. Moreover, in the same
setting, it is UG-hard to obtain an (๐ก โ ๐)-approximation, for any ๐ก โฅ 2 and ๐ > 0.
Corollary 3.13. It is NP-hard to obtain a (๐ก โ 1 โ ๐)-approximation for MWDS in ๐ก-interval graphs.
Moreover, in the same setting, it is UG-hard to obtain an (๐ก โ ๐)-approximation, for any ๐ก โฅ 2 and ๐ > 0.
Proof. We slightly modify the preceding reduction from ๐ก-uniform MWSC to the Red-Blue
Dominating Set problem. For each red interval ๐
๐ we also add a green point ๐บ ๐ that coincides
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 12
A LGORITHMS FOR I NTERSECTION G RAPHS OF ๐ก-I NTERVALS AND ๐ก-P SEUDODISKS
with ๐ฆ ๐ , the left end point of ๐
๐ , and we set its weight to 0. We set the weight of each blue ๐ก-point
to be twice the total weight of all the sets in the MWSC instance (conceptually the weight is โ).
The MWDS instance now consits of the red intervals, the blue ๐ก-points, and the green points.
The green points have zero weight and hence picking all of them will ensure that all green
points and red intervals are dominated. The green points cannot cover any of the blue points.
Since the blue ๐ก-points have very large weight, it is cheaper to pick all the red intervals than pick
any of them. Thus we can restrict attention to dominating sets that include all the green points
and a subset of the red intervals which together cover the blue ๐ก-points. Thus, ๐ก-uniform MWSC
reduces in an approximation preserving fashion to MWDS in ๐ก-interval graphs.
4 Maximum-Weight Independent Set
We consider MWIS of ๐ก-objects. Here, we are given a set ๐ฎ = {๐1 , . . . , ๐๐ }, where each ๐ ๐ โ ๐ฎ is
a ๐ก-object, and has a non-negative weight ๐ค ๐ . In this section, we assume that we are given the
geometric representation of the ๐ก-objects in ๐ฎ. The goal is to find maximum-weight independent
set ๐ฎ 0 โ ๐ฎ in the intersection graph of ๐ฎ.
We confine attention to the case when the base objects are closed Jordan domains. Let ๐ฑ(๐ฎ)
denote the set of vertices on ๐๐ฐ(๐ฎ). First, we describe a natural LP relaxation for this problem
(see for instance [12]).
ร
maximize ๐ค๐ ๐ฅ๐
๐ ๐ โ๐ฎ
ร
subject to ๐ฅ ๐ โค 1, โ๐ โ ๐ฑ(๐ฎ) (4.1)
๐ ๐ 3๐
๐ฅ ๐ โ [0, 1], โ๐ ๐ โ ๐ฎ (4.2)
We will assume that the preceding LP relaxation can be solved in polynomial time for
instances of interest. This is easy to see for geometric settings in which the vertices of the
arrangement ๐ฎ can be explicitly computed in polynomial time.
We have a simple observation that relates the union complexities of ๐ก-objects and the
corresponding (1-)objects.
Observation 4.1. Let ๐ฎ be a set of ๐ก-objects, and suppose the set of underlying (1-)objects has union
complexity ๐ข(ยท). Then, the union complexity of any ๐ objects in ๐ฎ is at most ๐ข(๐๐ก).
(๐)
Proof. Let โ โ ๐ฎ be any subset of ๐ก-objects. Let โ 0 = {๐ ๐ โ ๐
๐ : ๐
๐ โ ๐
} denote the underlying
set of (1-)objects. Note that |๐
0 | โค ๐ก ยท |๐
|. Since the underlying set of (1-)objects has union
complexity ๐ข(ยท), the number of arcs on the boundary of ๐
0 is at most ๐ข(|๐
0 |) โค ๐ข(๐ก ยท |๐
|).
Chan and Har-Peled [12] describe an algorithm to round a feasible fractional solution to the
LP relaxation which leads to the following guarantee.
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 13
C HANDRA C HEKURI AND TANMAY I NAMDAR
Theorem 4.2 (Chan and Har-Peled [12]). There is a polynomial-time ฮฉ(๐/๐ข(๐))-approximation
algorithm for MWIS in the intersection graph of a set of ๐ closed Jordan domains with union complexity
๐ข(ยท).
In particular, this implies an ฮฉ(1)-approximation for MWIS in the intersection graph of
pseudodisks, since pseudodisks have linear union complexity [3, 27]. However, we cannot use
the theorem directly, since a ๐ก-pseudodisk is not necessarily a closed Jordan domain. Although
the result in [12] easily extends to our setting via Observation 4.1, for the sake of completeness,
we briefly sketch the main reason. The following following technical lemma from [12] is the
main ingredient in the proof of Theorem 4.2.
Lemma 4.3 (Lemma 4.1 from [12]). Let ๐ฎ be a set of closed Jordan domains, and let {๐ฅ ๐ : ๐ ๐ โ ๐ฎ} be a
feasible solution to the MWIS LP relaxation. Furthermore, let โ โ ๐ฎ be any subset. Then, there is a
universal constant ๐ such that (๐,๐,๐)โ๐ฑ(โ) ๐ฅ ๐ ๐ฅ ๐ โค ๐ ยท ๐ข(โฐ(โ)), where โฐ(โ) = ๐๐ โโ ๐ฅ ๐ , and (๐, ๐, ๐)
ร ร
denotes a vertex ๐ formed by the intersection of closed Jordan domains ๐ ๐ and ๐ ๐ in the arrangement
๐ฑ(โ).
Lemma 4.3 is the only place in the proof of Theorem 4.2 which uses the assumption that ๐ฎ
is a set of closed Jordan domains. In other words, a bound on (๐,๐,๐)โ๐ฑ(โ) ๐ฅ ๐ ๐ฅ ๐ in terms of the
ร
union complexity, as in the statement of the lemma, readily implies an ฮฉ(๐/๐ข(๐))-approximation
for the respective set of objects. We need the generalization of Lemma 4.3 which works when
๐ฎ is a collection of ๐ก-pseudodisks. The proof of the lemma is based on a simple yet clever
random sampling argument and does not rely on the objects being closed Jordan domains.
Thus, the lemma holds when ๐ฎ is a collection of ๐ก-pseudodisks; indeed the lemma holds for
๐ก-objects where each object is a closed Jordan domain. We can therefore infer an ฮฉ(๐/๐ข(๐))
approximation for MWIS in the intersection graph of ๐ ๐ก-pseudodisks, where ๐ข(ยท) denotes the
union complexity of ๐ก-pseudodisks.
Finally, recall that pseudodisks have linear union complexity [3, 27]. Therefore, Observa-
tion 4.1, implies that a collection of ๐ ๐ก-pseudodisks have ๐(๐๐ก) union complexity. Therefore,
we get the following theorem.
Theorem 4.4. There is a polynomial-time ฮฉ(1/๐ก)-approximation algorithm for MWIS in the intersection
graph of ๐ก-pseudodisks.
Packing ๐ก-objects. We consider a related problem called Maximum-Weight Region Packing. We
are given a set ๐ฎ of ๐ก-objects, and a set of points ๐. Each ๐ก-object ๐ ๐ has a weight ๐ค ๐ and each
point ๐ โ ๐ has a capacity ๐(๐), which is a positive integer. The goal is to find a maximum-weight
set ๐ฎ 0 of ๐ก-objects, such that for each point ๐ โ ๐, the number of regions of ๐ฎ 0 that contain
๐ is at most ๐(๐). Note that MWIS is a special case when ๐ = ๐ฑ(๐) is the set of all points in
arrangement and ๐(๐) = 1 for each ๐ โ ๐.
Extending the LP rounding algorithm of Chan and Har-Peled [12] for the MWIS problem, Ene
๐ 1/๐ถ
et al. [17] gave an ฮฉ(( ๐ข(๐) ) )-approximation for Maximum-Weight Region Packing problem,
where ๐ถ is the minimum capacity of any point. Using similar arguments as in MWIS, we obtain
the following result.
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 14
A LGORITHMS FOR I NTERSECTION G RAPHS OF ๐ก-I NTERVALS AND ๐ก-P SEUDODISKS
Theorem 4.5. There is a polynomial-time ฮฉ(1/๐ก 1/๐ถ )-approximation algorithm for Maximum-Weight
Region Packing with ๐ก-pseudodisks.
5 Concluding remarks
In geometric settings, quasi-uniform sampling has been used for Set Multicover [7], and other
related ideas have been used for Partial Set Cover [24, 14]. Our results for MWDS and MWSC
for ๐ก-objects can be extended to these settings. We briefly sketch the ideas.
The results in [24, 14] establish a generic high-level reduction: an ๐ผ-approximation via the
natural LP relaxation for MWSC can be translated into an ๐(๐ผ)-approximation for Partial Set
Cover for hereditary instances. The geometric instances considered here are hereditary, and
hence our results for MWSC extend to Partial Set Cover.
Set Multicover is a generalization of Set Cover. In the geometric setting of interest here,
each point ๐ has integer demand ๐ ๐ โฅ 1, and the goal is to choose a minimum-weight subset
of objects so that each point is contained in at least ๐ ๐ objects. Bansal and Pruhs [7] extended
the shallow-cell complexity based framework from Set Cover to Set Multicover. Since we prove
our results by establishing shallow-cell complexity for ๐ก-objects, the results in [7] extend to Set
Multicover with ๐ก-pseudodisks.
Finally, we note that even for the special case of MWDS of ๐ก-intervals, there is a gap between
the upper and lower bounds on polynomial-time approximation ratios that we established in
this paper: ๐(๐ก log ๐ก) and ฮฉ(๐ก). Resolving this gap is an interesting open question. Obtaining
smaller leading constants in the approximation ratios, and avoiding the somewhat complicated
machinery of union complexity, for special cases such as ๐ก-intervals, is also of interest.
Acknowledgements: We thank Laci Babai for several suggestions and comments that improved
the clarity of the paper.
References
[1] Anna Adamaszek, Sariel Har-Peled, and Andreas Wiese: Approximation schemes
for independent set and sparse subsets of polygons. J. ACM, 66(4):29:1โ40, 2019.
[doi:10.1145/3326122] 5
[2] Anna Adamaszek and Andreas Wiese: Approximation schemes for maximum weight
independent set of rectangles. In Proc. 54th FOCS, pp. 400โ409. IEEE Comp. Soc., 2013.
[doi:10.1109/FOCS.2013.50] 5
[3] Pankaj K. Agarwal, Jรกnos Pach, and Micha Sharir: State of the union (of geometric
objects): A review. In Jacob E. Goodman, Jรกnos Pach, and Richard Pollack, editors,
Surveys in Discrete and Computational Geometry: Twenty Years Later, pp. 9โ48. Amer. Math.
Soc., 2007. Volume DOI. 5, 7, 14
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 15
C HANDRA C HEKURI AND TANMAY I NAMDAR
[4] Boris Aronov, Mark de Berg, Esther Ezra, and Micha Sharir: Improved bounds for
the union of locally fat objects in the plane. SIAM J. Comput., 43(2):543โ572, 2014.
[doi:10.1137/120891241] 7, 11
[5] Boris Aronov, Anirudh Donakonda, Esther Ezra, and Rom Pinchasi: On pseudo-disk
hypergraphs. Comput. Geom., 92:101687, 2021. [doi:10.1016/j.comgeo.2020.101687] 5, 6, 10
[6] Nikhil Bansal, Anupam Gupta, and Guru Guruganesh: On the Lovรกsz theta func-
tion for independent sets in sparse graphs. SIAM J. Comput., 47(3):1039โ1055, 2018.
[doi:10.1137/15M1051002] 5
[7] Nikhil Bansal and Kirk Pruhs: Weighted geometric set multi-cover via quasi-uniform
sampling. J. Comput. Geom., 7(1):221โ236, 2016. [doi:10.20382/jocg.v7i1a11] 15
[8] Reuven Bar-Yehuda, Magnรบs M. Halldรณrsson, Joseph Naor, Hadas Shachnai,
and Irina Shapira: Scheduling split intervals. SIAM J. Comput., 36(1):1โ15, 2006.
[doi:10.1137/S0097539703437843] 2, 5
[9] Reuven Bar-Yehuda and Dror Rawitz: Using fractional primal-dual to sched-
ule split intervals with demands. Discr. Optimization, 3(4):275โ287, 2006.
[doi:10.1016/j.disopt.2006.05.010] 2, 4
[10] Ayelet Butman, Danny Hermelin, Moshe Lewenstein, and Dror Rawitz: Optimiza-
tion problems in multiple-interval graphs. ACM Trans. Algorithms, 6(2):40:1โ18, 2010.
[doi:10.1145/1721837.1721856] 2, 3, 4, 7, 8, 10, 11
[11] Timothy M. Chan, Elyot Grant, Jochen Kรถnemann, and Malcolm Sharpe: Weighted
capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In
Proc. 23rd Ann. ACMโSIAM Symp. on Discrete Algorithms (SODAโ12), pp. 1576โ1585. SIAM,
2012. [doi:10.1137/1.9781611973099.125] 3, 5, 9, 11
[12] Timothy M. Chan and Sariel Har-Peled: Approximation algorithms for Maximum Inde-
pendent Set of pseudo-disks. Discr. Comput. Geom., 48(2):373โ392, 2012. [doi:10.1007/s00454-
012-9417-5] 3, 5, 13, 14
[13] Chandra Chekuri, Kenneth L. Clarkson, and Sariel Har-Peled: On the set mul-
ticover problem in geometric settings. ACM Trans. Algorithms, 9(1):9:1โ17, 2012.
[doi:10.1145/2390176.2390185] 5
[14] Chandra Chekuri, Kent Quanrud, and Zhao Zhang: On approximating partial set cover
and generalizations, 2019. [arXiv:1907.04413] 15
[15] Kenneth L. Clarkson and Kasturi R. Varadarajan: Improved approximation algorithms
for geometric set cover. Discr. Comput. Geom., 37(1):43โ58, 2007. [doi:10.1007/s00454-006-
1273-8] 5
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 16
A LGORITHMS FOR I NTERSECTION G RAPHS OF ๐ก-I NTERVALS AND ๐ก-P SEUDODISKS
[16] Irit Dinur, Venkatesan Guruswami, Subhash Khot, and Oded Regev: A new multilayered
PCP and the hardness of hypergraph vertex cover. SIAM J. Comput., 34(5):1129โ1146, 2005.
[doi:10.1137/S0097539704443057] 12
[17] Alina Ene, Sariel Har-Peled, and Benjamin Raichel: Geometric packing under nonuniform
constraints. SIAM J. Comput., 46(6):1745โ1784, 2017. [doi:10.1137/120898413] 14
[18] Uriel Feige: A threshold of ln ๐ for approximating set cover. J. ACM, 45(4):634โ652, 1998.
[doi:10.1145/285055.285059] 4, 5
[19] Uriel Feige: Approximating maximum clique by removing subgraphs. SIAM J. Discr. Math.,
18(2):219โ225, 2004. [doi:10.1137/S089548010240415X] 5
[20] Matt Gibson and Imran A. Pirwani: Algorithms for dominating set in disk graphs: Breaking
the log ๐ barrier. In Proc. 18th Eur. Symp. Algorithms (ESAโ10), pp. 243โ254. Springer, 2010.
[doi:10.1007/978-3-642-15775-2_21] 5
[21] Jerrold R. Griggs and Douglas B. West: Extremal values of the interval number of a graph.
SIAM J. Algebr. Discr. Methods, 1(1):1โ7, 1980. [doi:10.1137/0601001] 2
[22] Johan Hรฅstad: Clique is hard to approximate within ๐ 1โ๐ . Acta Math., 182(1):105โ142, 1999.
[doi:10.1007/BF02392825] 5
[23] Dorit S. Hochbaum and Asaf Levin: Cyclical scheduling and multi-shift scheduling:
Complexity and approximation algorithms. Discr. Optimization, 3(4):327โ340, 2006.
[doi:10.1016/j.disopt.2006.02.002] 4, 11
[24] Tanmay Inamdar and Kasturi R. Varadarajan: On partial covering for geometric set
systems. In Proc. 34th Internat. Symp. Comput. Geom. (SoCGโ18), pp. 47:1โ14. Schloss
DagstuhlโLeibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.SoCG.2018.47] 15
[25] Frank Kammer and Torsten Tholey: Approximation algorithms for intersection graphs.
Algorithmica, 68(2):312โ336, 2014. Preliminary version in [26]. [doi:10.1007/s00453-012-
9671-1] 2, 4
[26] Frank Kammer, Torsten Tholey, and Heiko Voepel: Approximation algorithms for
intersection graphs. In Proc. 13th Internat. Workshop on Approximation Algorithms for Combinat.
Opt. Probl. (APPROXโ10), pp. 260โ273. Springer, 2010. [doi:10.1007/978-3-642-15369-3_20]
2, 3, 5, 17
[27] Klara Kedem, Ron Livne, Jรกnos Pach, and Micha Sharir: On the union of Jordan regions
and collision-free translational motion amidst polygonal obstacles. Discr. Comput. Geom.,
1:59โ70, 1986. [doi:10.1007/BF02187683] 5, 7, 14
[28] Subhash Khot: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp.
767โ775. ACM Press, 2002. [doi:10.1145/509907.510017] 4
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 17
C HANDRA C HEKURI AND TANMAY I NAMDAR
[29] Subhash Khot and Oded Regev: Vertex cover might be hard to approximate to within 2 โ ๐.
J. Comput. System Sci., 74(3):335โ349, 2008. [doi:10.1016/j.jcss.2007.06.019] 4, 12
[30] Dana Moshkovitz: The Projection Games Conjecture and the NP-hardness
of ln ๐-approximating set-cover. Theory of Computing, 11(7):221โ235, 2015.
[doi:10.4086/toc.2015.v011a007] 4, 5
[31] Nabil H. Mustafa and Kasturi R. Varadarajan: Epsilon-approximations and epsilon-nets.
In Jacob E. Goodman, Joseph OโRourke, and Csaba D. Tรณth, editors, Handbook of Discrete
and Computational Geometry. Chapman and Hall/CRC, 3rd edition, 2017. TaylorโFrancis.
[arXiv:1702.03676] 5
[32] Aniket Basu Roy, Sathish Govindarajan, Rajiv Raman, and Saurabh Ray: Packing
and covering with non-piercing regions. Discr. Comput. Geom., 60(2):471โ492, 2018.
[doi:10.1007/s00454-018-9983-2] 5
[33] Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency. 2003. Springer. 3,
11
[34] William P. Thurston: The Geometry and Topology of Three-Manifolds. 1979. Princeton U.
Press. 2
[35] Kasturi R. Varadarajan: Weighted geometric set cover via quasi-uniform sampling. In
Proc. 42nd STOC, pp. 641โ648. ACM Press, 2010. [doi:10.1145/1806689.1806777] 3, 5, 9
[36] Vijay V. Vazirani: Approximation Algorithms. Springer, 2013. 5
[37] David P. Williamson and David B. Shmoys: The Design of Approximation Algorithms. Cam-
bridge Univ. Press, 2011. LINK. 5
[38] Yuli Ye and Allan Borodin: Elimination graphs. ACM Trans. Algorithms, 8(2):14:1โ23, 2012.
[doi:10.1145/2151171.2151177] 3
[39] David Zuckerman: Linear degree extractors and the inapproximability of Max Clique
and chromatic number. Theory of Computing, 3(6):103โ128, 2007. Preliminary version in
STOCโ06. [doi:10.4086/toc.2007.v003a006] 5
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 18
A LGORITHMS FOR I NTERSECTION G RAPHS OF ๐ก-I NTERVALS AND ๐ก-P SEUDODISKS
AUTHORS
Chandra Chekuri
Professor
Department of Computer Science
University of Illinois at Urbana-Champaign
Urbana, Illinois, United States
chekuri illinois edu
https://chekuri.cs.illinois.edu/
Tanmay Inamdar5
Researcher
Department of Informatics,
University of Bergen
Bergen, Norway
Tanmay Inamdar uib no
ABOUT THE AUTHORS
Chandra Chekuri received his B. Tech in Computer Science and Engineering from
Indian Institute of Technology, Madras (now Chennai) in 1993 and received
his Ph. D. in Computer Science from Stanford University in 1998 under the
supervision of the late Rajeev Motwani. After finishing his Ph. D. he worked
eight formative years at Lucent Bell Labs before moving to the University of
Illinois. He mainly works in algorithm design, combinatorial optimization,
graphs, and mathematical programming.
Tanmay Inamdar received his Ph. D. in Computer Science from The University of
Iowa in 2020, where he was advised by Kasturi Varadarajan. Currently he is
working as a Researcher at The University of Bergen in Norway. His research
interests include Approximation Algorithms, Computational Geometry, and
Parameterized Algorithms.
5This work was done when the author was a Ph. D. student at The University of Iowa, during a visit to University
of Illinois, Urbana-Champaign.
T HEORY OF C OMPUTING, Volume 18 (18), 2022, pp. 1โ19 19