2
$\begingroup$

I have posted this question before but i don't feel i expressed my confusion clearly enough. So i would like to try and explain again. This is a proof of the minimum vertex cover for unit disk graphs being NP-complete.

The following lemma 2.1 is used

Lemma 2.1 (Valiant [19]). A planar graph $G$ with maximum degree 4 can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at integer coordinates and its edges are drawn so that they are made up of line segments of the form $x=i$ or $y=j$,for integers $i$ and $j$.

So in particular i'm now reading the section on UD vertex cover being NP hard (page 172)

THEOREM: UD Vertex cover is NP-Complete

Proof. The reduction is from PLANAR VERTEX COVER with maximum degree 3, which was shown NP-complete in [4]. As before, we transform the planar graph $G$ with maximum degree 3 to a unit disk graph $G’$ such that $G$ has a vertex cover $S$ with $|S|\leq k$ if and only if $G’$ has a vertex cover $S’$ with $|S'|\leq k’$.

We draw $G$ in the plane using Lemma 2.1. We then replace each edge $\{u, v\}$ by a path having an even number $2k_{uv}$,, of intermediate vertices, in such a way that an intersection model can be constructed. (This is clearly easy to do. Note, however, that a grid graph embedding will not be possible unless G is bipartite, which is why this construction does not work for grid graphs.) It is straightforward to verify that $G$ has a vertex cover $S$ such that $|S| <k$ if and only if $G’$ has a vertex cover $S’$ such that $|S'|\leq k+\sum_{uv \in E(G)} K_{uv}$.

So here is my confusion, they say the construction doesn't work for grid graphs, grid graphs here are unit disk graphs placed at integer co-ordinates on a grid with radius $1/2$. Firstly i want to make clear that i understand that the vertex cover problem on a grid graph is solvable in polynomial time as it is a bipartite graph. My question is if i placed a vertex at every integer point on the line between vertices $u$ and $v$ (similar to how they place $2k_{uv}$ disks on these lines) i would obtain a grid graph, so why is the problem so fundamentally different? Why does the condition that $G$ has a vertex cover $S$ such that $|S| <k$ if and only if $G’$ has a vertex cover $S’$ such that $|S'|\leq k+\sum_{uv \in E(G)} K_{uv}$ work for their construction but not for the construction i mentioned i.e where every edge is subdivided by integer co-ordinates to form a grid.

$\endgroup$
2
  • $\begingroup$ What is 'grid graph embedding'? $\endgroup$ Nov 29, 2014 at 19:08
  • 1
    $\begingroup$ They don't eloborate on anything beyond what i've copied, but this is a good question perhaps something im not too sure on myself. $\endgroup$ Nov 29, 2014 at 22:27

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.