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

Jana Cslovjecsek, Michał Pilipczuk, Karol Węgrzycki

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…