Intersection graphs of planar geometric objects such as intervals,
disks, rectangles and pseudodisks are wellstudied. 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 multipleinterval graphs.
Subsequent work by Kammer et al.\ (APPROXRANDOM 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
\emph{minimumweight dominating set problem}
in $t$interval graphs, we obtain a
polynomialtime
$O(t \log t)$approximation algorithm,
improving upon the previously known
polynomialtime $t^2$approximation by
Butman et al.
In the same class of graphs we show that it is $\NP$hard
to obtain a $(t1\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
\emph{maximumweight 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.
more »
« less
Independent Sets in Elimination Graphs with a Submodular Objective
Maximum weight independent set (MWIS) admits a 1/kapproximation in inductively kindependent graphs [Karhan Akcoglu et al., 2002; Ye and Borodin, 2012] and a 1/(2k)approximation in kperfectly orientable graphs [Kammer and Tholey, 2014]. These are a parameterized class of graphs that generalize kdegenerate graphs, chordal graphs, and intersection graphs of various geometric shapes such as intervals, pseudodisks, and several others [Ye and Borodin, 2012; Kammer and Tholey, 2014]. We consider a generalization of MWIS to a submodular objective. Given a graph G = (V,E) and a nonnegative submodular function f: 2^V → ℝ_+, the goal is to approximately solve max_{S ∈ ℐ_G} f(S) where ℐ_G is the set of independent sets of G. We obtain an Ω(1/k)approximation for this problem in the two mentioned graph classes. The first approach is via the multilinear relaxation framework and a simple contention resolution scheme, and this results in a randomized algorithm with approximation ratio at least 1/e(k+1). This approach also yields parallel (or lowadaptivity) approximations.
Motivated by the goal of designing efficient and deterministic algorithms, we describe two other algorithms for inductively kindependent graphs that are inspired by work on streaming algorithms: a preemptive greedy algorithm and a primaldual algorithm. In addition to being simpler and faster, these algorithms, in the monotone submodular case, yield the first deterministic constant factor approximations for various special cases that have been previously considered such as intersection graphs of intervals, disks and pseudodisks.
more »
« less
 Award ID(s):
 2129816
 NSFPAR ID:
 10500359
 Editor(s):
 Megow, Nicole; Smith, Adam
 Publisher / Repository:
 Schloss Dagstuhl – LeibnizZentrum für Informatik
 Date Published:
 Journal Name:
 Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023, September 1113, 2023, Atlanta, Georgia, USA
 Subject(s) / Keyword(s):
 elimination graphs independent set submodular maximization primaldual Theory of computation → Graph algorithms analysis Theory of computation → Submodular optimization and polymatroids
 Format(s):
 Medium: X
 Location:
 Atlanta, Georgia, USA
 Sponsoring Org:
 National Science Foundation
More Like this


Mulzer, Wolfgang ; Phillips, Jeff M (Ed.)Finding the diameter of a graph in general cannot be done in truly subquadratic assuming the Strong Exponential Time Hypothesis (SETH), even when the underlying graph is unweighted and sparse. When restricting to concrete classes of graphs and assuming SETH, planar graphs and minorfree graphs admit truly subquadratic algorithms, while geometric intersection graphs of unit balls, congruent equilateral triangles, and unit segments do not. Unitdisk graphs is one of the major open cases where the complexity of diameter computation remains unknown. More generally, it is conjectured that a truly subquadratic time algorithm exists for pseudodisk graphs where each pair of objects has at most two intersections on the boundary. In this paper, we show a trulysubquadratic algorithm of running time O^~(n^{21/18}), for finding the diameter in a unitdisk graph, whose output differs from the optimal solution by at most 2. This is the first algorithm that provides an additive guarantee in distortion, independent of the size or the diameter of the graph. Our algorithm requires two important technical elements. First, we show that for the intersection graph of pseudodisks, the graph VCdimension  either of khop balls or the distance encoding vectors  is 4. This contrasts to the VC dimension of the pseudodisks themselves as geometric ranges (which is known to be 3). Second, we introduce a cliquebased rclustering for geometric intersection graphs, which is an analog of the rdivision construction for planar graphs. We also showcase the new techniques by establishing new results for distance oracles for unitdisk graphs with subquadratic storage and O(1) query time. The results naturally extend to unit L₁ or L_∞disks and fat pseudodisks of similar size. Last, if the pseudodisks additionally have bounded ply, we have a truly subquadratic algorithm to find the exact diameter.more » « less

Evans, Robin ; Shpitser, Ilya (Ed.)We consider the problem of maximizing submodular functions under submodular constraints by formulating the problem in two ways: \SCSKC and \DiffC. Given two submodular functions $f$ and $g$ where $f$ is monotone, the objective of \SCSKC problem is to find a set $S$ of size at most $k$ that maximizes $f(S)$ under the constraint that $g(S)\leq \theta$, for a given value of $\theta$. The problem of \DiffC focuses on finding a set $S$ of size at most $k$ such that $h(S) = f(S)g(S)$ is maximized. It is known that these problems are highly inapproximable and do not admit any constant factor multiplicative approximation algorithms unless NP is easy. Known approximation algorithms involve datadependent approximation factors that are not efficiently computable. We initiate a study of the design of approximation algorithms where the approximation factors are efficiently computable. For the problem of \SCSKC, we prove that the greedy algorithm produces a solution whose value is at least $(11/e)f(\OPT)  A$, where $A$ is the datadependent additive error. For the \DiffC problem, we design an algorithm that uses the \SCSKC greedy algorithm as a subroutine. This algorithm produces a solution whose value is at least $(11/e)h(\OPT)B$, where $B$ is also a datadependent additive error. A salient feature of our approach is that the additive error terms can be computed efficiently, thus enabling us to ascertain the quality of the solutions produced.more » « less

Given two (di)graphs G, H and a cost function c:V(G) x V(H) > Q_{>= 0} cup {+infty}, in the minimum cost homomorphism problem, MinHOM(H), we are interested in finding a homomorphism f:V(G)> V(H) (a.k.a Hcoloring) that minimizes sum limits_{v in V(G)}c(v,f(v)). The complexity of exact minimization of this problem is well understood [Pavol Hell and Arash Rafiey, 2012], and the class of digraphs H, for which the MinHOM(H) is polynomial time solvable is a small subset of all digraphs. In this paper, we consider the approximation of MinHOM within a constant factor. In terms of digraphs, MinHOM(H) is not approximable if H contains a digraph asteroidal triple (DAT). We take a major step toward a dichotomy classification of approximable cases. We give a dichotomy classification for approximating the MinHOM(H) when H is a graph (i.e. symmetric digraph). For digraphs, we provide constant factor approximation algorithms for two important classes of digraphs, namely biarc digraphs (digraphs with a conservative semilattice polymorphism or minordering), and karc digraphs (digraphs with an extended minordering). Specifically, we show that:  Dichotomy for Graphs: MinHOM(H) has a 2V(H)approximation algorithm if graph H admits a conservative majority polymorphims (i.e. H is a biarc graph), otherwise, it is inapproximable;  MinHOM(H) has a V(H)^2approximation algorithm if H is a biarc digraph;  MinHOM(H) has a V(H)^2approximation algorithm if H is a karc digraph. In conclusion, we show the importance of these results and provide insights for achieving a dichotomy classification of approximable cases. Our constant factors depend on the size of H. However, the implementation of our algorithms provides a much better approximation ratio. It leaves open to investigate a classification of digraphs H, where MinHOM(H) admits a constant factor approximation algorithm that is independent of V(H).more » « less

Given two (di)graphs G, H and a cost function c:V(G) x V(H) > Q_{>= 0} cup {+infty}, in the minimum cost homomorphism problem, MinHOM(H), we are interested in finding a homomorphism f:V(G)> V(H) (a.k.a Hcoloring) that minimizes sum limits_{v in V(G)}c(v,f(v)). The complexity of exact minimization of this problem is well understood [Pavol Hell and Arash Rafiey, 2012], and the class of digraphs H, for which the MinHOM(H) is polynomial time solvable is a small subset of all digraphs. In this paper, we consider the approximation of MinHOM within a constant factor. In terms of digraphs, MinHOM(H) is not approximable if H contains a digraph asteroidal triple (DAT). We take a major step toward a dichotomy classification of approximable cases. We give a dichotomy classification for approximating the MinHOM(H) when H is a graph (i.e. symmetric digraph). For digraphs, we provide constant factor approximation algorithms for two important classes of digraphs, namely biarc digraphs (digraphs with a conservative semilattice polymorphism or minordering), and karc digraphs (digraphs with an extended minordering). Specifically, we show that:  Dichotomy for Graphs: MinHOM(H) has a 2V(H)approximation algorithm if graph H admits a conservative majority polymorphims (i.e. H is a biarc graph), otherwise, it is inapproximable;  MinHOM(H) has a V(H)^2approximation algorithm if H is a biarc digraph;  MinHOM(H) has a V(H)^2approximation algorithm if H is a karc digraph. In conclusion, we show the importance of these results and provide insights for achieving a dichotomy classification of approximable cases. Our constant factors depend on the size of H. However, the implementation of our algorithms provides a much better approximation ratio. It leaves open to investigate a classification of digraphs H, where MinHOM(H) admits a constant factor approximation algorithm that is independent of V(H).more » « less