Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs

We consider two optimization problems in planar graphs. In Maximum Weight Independent Set of Objects we are given a graph G and a family \({\mathcal {D}}\) of objects, each being a connected subgraph of G with a prescribed weight, and the task is to find a maximum-weight subfamily of \({\mathcal {D}}\) consisting of pairwise disjoint objects. In Minimum Weight Distance Set Cover we are given a graph G in which the edges might have different lengths, two sets \({\mathcal {D}},{\mathcal {C}}\) of vertices of G, where vertices of \({\mathcal {D}}\) have prescribed weights, and a nonnegative radius r. The task is to find a minimum-weight subset of \({\mathcal {D}}\) such that every vertex of \({\mathcal {C}}\) is at distance at most r from some selected vertex. Via simple reductions, these two problems generalize a number of geometric optimization tasks, notably Maximum Weight Independent Set for polygons in the plane and Weighted Geometric Set Cover for unit disks and unit squares. We present quasi-polynomial time approximation schemes (QPTASs) for both of the above problems in planar graphs: given an accuracy parameter \(\epsilon >0\) we can compute a solution whose weight is within multiplicative factor of \((1+\epsilon )\) from the optimum in time \(2^{{\mathrm {poly}}(1/\epsilon ,\log |{\mathcal {D}}|)}\cdot n^{{\mathcal {O}}(1)}\), where n is the number of vertices of the input graph. We note that a QPTAS for Maximum Weight Independent Set of Objects would follow from existing work. However, our main contribution is to provide a unified framework that works for both problems in both a planar and geometric setting and to transfer the techniques used for recursive approximation schemes for geometric problems due to Adamaszek and Wiese (in Proceedings of the FOCS 2013, IEEE, 2013; in Proceedings of the SODA 2014, SIAM, 2014) and Har-Peled and Sariel (in Proceedings of the SOCG 2014, SIAM, 2014) to the setting of planar graphs. In particular, this yields a purely combinatorial viewpoint on these methods as a phenomenon in planar graphs.

1. For every pair of vertices \(u^{\prime},v^{\prime}\) with \({\text {dist}}(u^{\prime},v^{\prime})\le r\), if \(\{v:{\text {dist}}(u^{\prime},v)\le r/2\} \cap \{v:{\text {dist}}(v^{\prime},v)\le r/2\}=\emptyset \) then we subdivide the middle edge of the shortest path between \(u^{\prime}\) and \(v^{\prime}\) such that the sets \(\{v:{\text {dist}}(u^{\prime},v)\le r/2\}, \{v:{\text {dist}}(v^{\prime},v)\le r/2\}\) intersect on the new vertex. This way we add at most \(O(n^2)\) new vertices to the instance.

2. Obviously, edge lengths are immaterial for the MWISO problem. However, it is convenient to think of G as a graph whose edges have lengths so that we can define Voronoi diagrams. Furthermore, many results of this section will be reused for the MWDSC problem, where edge lengths do play a role.

We thank Dániel Marx for insightful discussions on the approach to optimization problems in geometric and planar settings via Voronoi diagrams.

Authors and Affiliations

1. Institute of Informatics, University of Warsaw, Warsaw, Poland

   Michał Pilipczuk

2. Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands

   Erik Jan van Leeuwen

3. Department of Industrial Engineering and Center for Mathematical Modeling, Universidad de Chile, Santiago de Chile, Chile

   Andreas Wiese

Corresponding author

Correspondence to Andreas Wiese.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The work of Mi. Pilipczuk on these results was, at the initial stages, partially supported by Polish National Science Centre grant UMO-2013/11/D/ST6/03073, and, at the later stages, was a part of project TOTAL that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 677651). The research of A. Wiese is supported by the Millennium Nucleus Information and Coordination in Networks ICM/FIC RC130003 and by the grant Fondecyt Regular 1170223.

Appendix: Geometric Problems

In the Maximum Weight Independent Set of Polygons (MWISP) problems we are given a family \({\mathcal {P}}\) of polygons in the plane, each with a prescribed weight, and the task is to find a maximum-weight subset of pairwise disjoint polygons. In the Weighted Geometric Set Cover problem we are given a family \({\mathcal {P}}\) of subsets of the plane, each with a prescribed weight, and a set \({\mathcal {U}}\) of points in the plane. The goal is to find a minimum-weight subfamily of \({\mathcal {P}}\) whose union covers \({\mathcal {U}}\). A QPTAS for MWISP with running time \(2^{{{\mathrm {poly}}}(1/\epsilon ,\log N)}\cdot n^{{\mathcal {O}}(1)}\), where \(N=|{\mathcal {P}}|\) and n is the total number of vertices of the input polygons, was given by Har-Peled [4]. A QPTAS for WGSR under the assumption that \({\mathcal {P}}\) is a family of pseudo-disks (i.e. compact, simply connected subsets of the plane such that the boundaries of each two meet in at most two points) with running time \(2^{{{\mathrm {poly}}}(1/\epsilon ,n+N)}\), where \(n=|{\mathcal {U}}|\) and \(N=|{\mathcal {P}}|\), was given by Mustafa et al. [7].

We now prove that the abovementioned results follow from Theorems 1 and 2 via simple reductions from the geometric to the planar setting; the exception is that for WGSR we can tackle only unit disks and unit squares instead of general pseudo-disks. These reductions were already observed by Marx and Pilipczuk in [5], who used them for the parameterized variants of the problems. We give them for completeness.

Corollary 1

TheMaximum Weight Independent Set of Polygonsproblem admits a QPTAS with running time\(2^{{{\mathrm {poly}}}(1/\epsilon ,\log N)}\cdot n^{{\mathcal {O}}(1)}\), whereNis the number of polygons andnis the total number of vertices of those polygons.

Corollary 2

TheWeighted Geometric Set Coverproblems for unit disks and axis-parallel unit squares admits a QPTAS with running time\(2^{{{\mathrm {poly}}}(1/\epsilon ,\log N)}\cdot n^{{\mathcal {O}}(1)}\), whereNis the number of disks/squares on input andnis the number of points to be covered.

Before we proceed to proving the statements above, let us first give a general-use definition of the crossing graph of a point set in the plane; see Fig. 7. Consider a finite set of points X in the plane and a metric \(d(\cdot ,\cdot )\) on the plane induced by some norm (i.e. \(d(x,y)=\Vert x-y\Vert \) for some norm \(\Vert \cdot \Vert \)). By \(G\langle X,d\rangle \) we denote a graph defined as follows. For every pair of distinct points \(a,b\in X\), draw the segment with endpoints a and b in the plane. Let \(Y\supseteq X\) be the set consisting of X and all intersections of all the segments drawn; then set Y to be the vertex set of \(G\langle X,d\rangle \). Two points \(x,y\in Y\) are connected by an edge in \(G\langle X,d\rangle \) if they are two consecutive points from Y on any of the drawn segments; that is, the segment connecting x and y is contained in one of the segments connecting pairs of vertices from X, and there is no other point from Y inside this segment. The length of this edge is set to d(x, y). Note that \(G\langle X,d\rangle \) has at most \(|X|^4\) vertices, is planar with a straight-line embedding described above, and for every two vertices \(a,b\in X\) we have \({\text {dist}}_{G\langle X,d\rangle }(a,b)=d(a,b)\).

A point set X and the corresponding crossing graph \(G\langle X,d\rangle \), for an unspecified metric d. Note that two triples of points in X are collinear

Full size image

For further reference, let \(d_2(\cdot ,\cdot )\) and \(d_{\infty }(\cdot ,\cdot )\) denote the metrics on the plane induced by the \(\ell _2\)- and \(\ell _\infty \)-norm, respectively. We now prove Corollaries 1 and 2.

Proof (of Corollary 1)

Let \({{\mathcal {P}}}\) be the given weighted set of polygons and let X be the set of all their vertices; then \(|X|=n\). Consider the graph \(G=G\langle X,d_\infty \rangle \); note that G has at most \(n^4\) vertices. For every polygon \(P\in {{\mathcal {P}}}\) construct a corresponding object p in G defined as follows: p is the subgraph of G induced by all the vertices of G whose embeddings are contained in P. It is easy to see that p defined in this manner is connected. The weight of p is equal to the weight of P. Let \({\mathcal {D}}\) be the family comprising all the constructed objects. It readily follows that sets of pairwise disjoint polygons from \({{\mathcal {P}}}\) are in one-to-one correspondence with independent subfamilies of \({\mathcal {D}}\), hence it suffices to apply the algorithm of Theorem 1 to the instance \((G,{\mathcal {D}})\). \(\square \)

Proof (of Corollary 2)

Let us first concentrate on the case of unit disks. Let the input be \(({\mathcal {P}},{\mathcal {U}})\), where \({\mathcal {P}}\) is a weighted set of unit disks and \({\mathcal {U}}\) is a set of points to be covered. Let X be the set consisting of all the centers of disks from \({\mathcal {P}}\) and all the points from \({\mathcal {U}}\); then \(|X|\le N+n\). Consider the graph \(G=G\langle X,d_2\rangle \); note that G has at most \((N+n)^4\) vertices. Construct a weighted set of points \({\mathcal {D}}\) as follows: for every disk \(P\in {{\mathcal {P}}}\), add the center of P to \({\mathcal {D}}\) and assign it weight equal to the weight of P. It can be easily seen that a subset of disks \({{{\mathcal {Q}}}}\subseteq {\mathcal {P}}\) covers all the points from \({\mathcal {U}}\) if and only if the centers of disks from \({{{\mathcal {Q}}}}\) cover \({\mathcal {U}}\) in G, where we consider domination radius \(\frac{1}{2}\). Hence it suffices to apply the algorithm of Theorem 2 to the instance \((G,{\mathcal {D}},{\mathcal {U}},\frac{1}{2})\).

For the case of unit squares we may follow the same reasoning except we use metric \(d_\infty (\cdot ,\cdot )\) instead of \(d_2(\cdot ,\cdot )\). \(\square \)

Reprints and permissions