A polynomial-time $\text{OPT}^ε$-approximation algorithm for maximum independent set of connected subgraphs in a planar graph
Preprint
Abstract
In the Maximum Independent Set of Objects problem, we are given an $n$-vertex planar graph $G$ and a family $\mathcal{D}$ of $N$ 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 whose running time is bounded by $2^{\mathrm{poly}(\log(N),1/ε)} \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 Voronoi separators, introduced by Marx and Pilipczuk (TALG '22), with a new analysis of the approximation factor.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar GraphsAlgorithmica, 2020
- Approximation Schemes for Independent Set and Sparse Subsets of PolygonsJournal of the ACM, 2019
- Independent set of intersection graphs of convex objects in 2DComputational Geometry, 2006
- Polynomial-Time Approximation Schemes for Geometric Intersection GraphsSIAM Journal on Computing, 2005
- Polynomial-time approximation schemes for packing and piercing fat objectsJournal of Algorithms, 2003
- Clique is hard to approximate within n1−εActa Mathematica, 1999
- Label placement by maximum independent set in rectanglesComputational Geometry, 1998
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problemsJournal of the ACM, 1998
- Approximation schemes for covering and packing problems in image processing and VLSIJournal of the ACM, 1985