I'm attempting a reduction from the vertex cover problem to the guard cover problem
guard cover:
instance: a graph G and a bound k
question: is there a subset S of at most k vertices such that every vertex of G is separated from a vertex of S by a path of at most two edges?
The purpose of the reduction is to show that Guard Cover is NP-complete (I can assume that vertex cover is np-complete)
First i must show that Guard Cover is in NP:
I believe the way to do this is to simply take an instance of a solution to the problem, namely a graph and a set of vertices in the graph, and for each vertex, remove every edge that can be reached within two or less vertices from that edge. I am not sure if this would qualify as verification in polynomial time.
Next i must reduce vertex cover to guard cover in polynomial time:
so i need to take an instance of vertex cover, and convert it to an instance of guard cover, such that giving an answer to the guard cover decision problem would give an answer to the vertex cover decision problem.
I'm a bit lost as to where i should start, i have the intuition that i will have to add edges to the graph of the vertex cover instance, because this seems to be a matter of traversing two edges in the case of guard cover, whereas a guard in the vertex cover problem would only be able to traverse one edge.
Any thoughts would be greatly appreciated.
Thanks!