World's most popular travel blog for travel bloggers.

[Solved]: Transforming an arbitrary cover into a vertex cover

, , No Comments
Problem Detail: 

Given is a planar graph $G=(V,E)$ and let $\mathcal{G}$ denote its embedding in the plane s.t. each edge has length $1$. I have furthermore a set $C$ of points where each point $c \in C$ is contained in $\mathcal{G}$. Furthermore, it holds for any point $p$ in $\mathcal{G}$ that there exists a $c \in C$ with geodesic distance to $p$ at most one. (The distance is measured as the shortest distance within $\mathcal{G}$.)

I want to argue that given a $C$ for which the above condition holds, I can easily transform it into a vertex cover, or put differently, transform it into a $C'$ of same cardinality s.t any $c \in C'$ is placed in $\mathcal{G}$ at a vertex of $G$, and $C'$ still covers $G$.

My approach was to orient the edges and move the points in $C$ at the end vertex of the arc. But so far I did not find a correct orientation which yields $C'$ from $C$.

Does anybody have an idea?

Asked By : user695652

Answered By : mhum

If no points in $C$ lie exactly on the mid-point of an edge in $\mathcal{G}$, then it suffices to associate each point in $C$ to the nearest vertex in $\mathcal{G}$. I will leave it as an exercise to the reader to prove this (hint: prove by contradiction).

On the other hand, if points in $C$ are allowed to lie on the mid-point of edges, then we can provide a counter-example:

enter image description here

The blue lines and circles are $\mathcal{G}$ and the red crosses are $C$.

EDITED TO ADD: An example with a biconnected graph

enter image description here

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11347

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback