2023/10/31 by Jana Cslovjecsek, Michał Pilipczuk, Cslovjecsek, Jana +3 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2310.20325
openalex publication_date 2023/10/31 · openalex created_date 2023/11/02 · openalex updated_date 2026/07/30
In the Maximum Independent Set of Objects problem, we are given an n-vertex planar graph G and a family D of N objects, where each object is a connected subgraph of G. The task is to find a subfamily F ⊆ D of maximum cardinality that consists of pairwise disjoint objects. This problem is 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 quasi-polynomial time approximation scheme (QPTAS): a (1-ε)-approximation algorithm whose running time is bounded by 2poly(log(N),1/ε) ⋅ nO(1). Nevertheless, to the best of our knowledge, in the polynomial-time regime only the trivial 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ε-approximation algorithm with running time N^2^O(1/ε), for any ε>0. In this work, we present an OPTε-approximation algorithm for the problem that runs in time N^O(1/ε2) nO(1), for any ε>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.