# Reduction from Vertex Cover to Polygon Cover

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.

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.
• I am confused about the reduction, can you possibly give me an example for instance let's say $k=3$? – Boris Mikhail Apr 2 '15 at 1:46
• 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. – Pål GD Apr 2 '15 at 2:31
• 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. – Pål GD Apr 2 '15 at 2:53
• You said the points $P$ are the points where the vertices are drawn, are these the vertices in $G=(V,E)$? – Boris Mikhail Apr 2 '15 at 3:00
• Yes, in my reduction $P$ corresponds to the coordinates at which vertices of $V(G)$ are drawn. – Pål GD Apr 2 '15 at 3:09