A polynomial-time OPT ɛ -approximation algorithm for maximum independent set of connected subgraphs in a planar graph
Jana Cslovjecsek, Michał Pilipczuk, Karol Węgrzycki · Society for Industrial and Applied Mathematics eBooks · 2024
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.