5
$\begingroup$

Polygon Cover:

Input: A set of points $P$, a set of polygons $S$ in a 2D plane, and a positive integer $k \in \mathbb{N}$.

Output: True if and only if there exists a subset in $S$ of at most $k$ (not necessarily convex) polygons such that every point in $P$ lie inside some polygon in the subset.

I am trying to give a polynomial reduction from Vertex Cover to Polygon Cover. However, I am struggling slightly. My idea is that to construct the set of points $P$, I figured that I should map each $uv \in E$ with ($u < v$) to a point $(u, v)$. For the set of polygons $S$, I was thinking to define some type of non-convex polygon in order to cover the rows and columns.

$\endgroup$
1
$\begingroup$

Let $(G,k)$ be an instance of Dominating Set where $G$ is drawn on the plane with any drawing. Construct for each vertex $v$ a polygon $S_v$ which covers all of $N[v]$ and no other vertices, where $N[v]$ is the set containing $v$ and all its neighbors. Let $S = \bigcup_{v \in V(G)} S_v$ and the points $P$ be the points where the vertices are drawn. The instance for Polygon Cover is $P, S, k$. This reduction is a Karp-reduction from Dominating Set which is NP-complete, and hence Polygon Cover is NP-complete as well.

To formally prove that the above reduction works, you need to prove that selecting a set of $k$ polygons $S' \subseteq S$ which covers all the points corresponds to picking a set of vertices whose neighborhoods contain all the vertices of the graph.

If you want to prove it for convex polygons, you can use the fact that Dominating Set is NP-complete on planar graphs and that planar graphs are equivalent to kissing graphs.

$\endgroup$
  • $\begingroup$ I am confused about the reduction, can you possibly give me an example for instance let's say $k=3$? $\endgroup$ – Boris Mikhail Apr 2 '15 at 1:46
  • $\begingroup$ What is it you don't understand? Draw a graph on a piece of paper, and for each vertex $v$ draw a polygon that covers $N[v]$. Now, to cover all the vertices with polygons, you must select a dominating set of the graph. $\endgroup$ – Pål GD Apr 2 '15 at 2:31
  • $\begingroup$ Ps., if you want from vertex cover, you can draw a point on the middle of an edge $e$, and use the same construction as in my reduction, but with the differently places points. $\endgroup$ – Pål GD Apr 2 '15 at 2:53
  • $\begingroup$ You said the points $P$ are the points where the vertices are drawn, are these the vertices in $G=(V,E)$? $\endgroup$ – Boris Mikhail Apr 2 '15 at 3:00
  • $\begingroup$ Yes, in my reduction $P$ corresponds to the coordinates at which vertices of $V(G)$ are drawn. $\endgroup$ – Pål GD Apr 2 '15 at 3:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.