Campus Event Calendar

Event Entry

New for: D1

What and Who

A polynomial-time $\text{OPT}^\eps$-approximation algorithm for maximum independent set of connected subgraphs in a planar graph

Karol Węgrzycki
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Tuesday, 5 March 2024
30 Minutes
E1 4


In the \textsc{Maximum Independent Set of Objects} problem, we are given an $n$-vertex planar graph $G$ and a family $\mathcal{D}$ of $N$ \emph{objects}, where each object is a connected subgraph of $G$. The task is to find a subfamily $\mathcal{F} \subseteq \mathcal{D}$ of maximum cardinality that consists of pairwise disjoint objects. This problem is $\mathsf{NP}$-hard and is equivalent to the problem of finding the maximum number of pairwise disjoint polygons in a given family of polygons in the plane.

As shown by Adamaszek et al. (J. ACM '19), the problem admits a \emph{quasi-polynomial time approximation scheme} (QPTAS): a $(1-\varepsilon)$-approximation algorithm with running time \mbox{$2^{\mathrm{poly}(\log(N),1/\epsilon)} \cdot n^{\mathcal{O}(1)}$}. Nevertheless, to the best of our knowledge, in the polynomial-time regime only the trivial $\mathcal{O}(N)$-approximation is known for the problem in full generality. In the restricted setting where the objects are pseudolines in the plane, Fox and Pach (SODA '11) gave an $N^{\varepsilon}$-approximation algorithm with running time $N^{2^{\tilde{\mathcal{O}}(1/\varepsilon)}}$, for any $\varepsilon>0$.

In this work, we present an $\text{OPT}^{\varepsilon}$-approximation algorithm for the problem that runs in time $N^{\tilde{\mathcal{O}}(1/\varepsilon^2)} n^{\mathcal{O}(1)}$, for any $\varepsilon>0$, thus improving upon the result of Fox and Pach both in terms of generality and in terms of the running time. Our approach combines the methodology of \emph{Voronoi separators}, introduced by Marx and Pilipczuk (TALG '22), with a new analysis of the approximation factor.

Joint work with Jana Cslovjecsek and Michał Pilipczuk.


Nidhi Rathi
+49 681 9325 1134
--email hidden

Virtual Meeting Details

897 027 2575
passcode not visible
logged in users only

Uwe Brahm, 03/06/2024 00:33
Uwe Brahm, 03/05/2024 19:26
Uwe Brahm, 02/06/2024 18:22
Nidhi Rathi, 02/06/2024 15:55 -- Created document.