Member Avatar for cubixguy77
cubixguy77 0 Newbie Poster

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!

  • 1 Contributor
  • 0 Replies
  • 88 Views

Dani AI

Generated

A short, standard solution that answers both parts.

Verification (Guard Cover is in NP)

A certificate is a set S of vertices. Check |S| <= k and run a multi‑source breadth‑first search from S truncated at depth 2. Mark every vertex reached within 0, 1 or 2 edges and accept iff every vertex is marked. BFS from a set of sources runs in O(|V|+|E|) time, so verification is polynomial.

Polynomial reduction (Vertex Cover -> Guard Cover)

Given a Vertex Cover instance G=(V,E), ignore isolated vertices and build G' by subdividing every edge: for each edge (u,v) introduce a new vertex w{uv} and replace (u,v) by edges (u,w{uv}) and (w_{uv},v). Set k' = k. This subdivision is linear-time.

Correctness sketch

If C is a vertex cover of G with |C| <= k then the same C (viewed as vertices of G') is a distance‑2 dominating (guard) set: every subdivision vertex w_{uv} is adjacent to at least one endpoint in C, and any original vertex x not in C has a neighbor in C in G so in G' it is at distance 2 from that neighbor. Hence every vertex of G' is within distance <= 2 of C.

Conversely, any guard set S in G' of size <= k can be converted (without increasing size) to a set of original vertices that covers every original edge: every subdivision vertex w_{uv} must be within distance <= 2 of some s in S, and any such s is either u, v, or a subdivision vertex adjacent to u or v — so one can choose for each s an adjacent original endpoint and collect at most |S| endpoints that together include at least one endpoint of every original edge. Therefore the construction is a polynomial reduction, giving NP‑hardness; together with membership above, Guard Cover is NP‑complete. Guard Cover is just the distance‑2 dominating set problem (equivalently dominating set on the square G^2); see Dominating set for background.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.