V is either in D or adjacent to at least one member of D. Definition
Given an undirected graph G = (V,E), we say D ⊆ V is a dominating set if every
v V is either in D or adjacent to at least one member of D.
Polynomial Certifier
Given an undirected graph G = (V,E), does there exists a set D ⊆ V of size k,
such that if every v V is either in D or adjacent to at least one member of
D.
V is either in D or adjacent to at least one member of D.
Reduction from Vertex Cover from simple case to general case
Given a graph G = (V,E) has an instance of Vertex Cover of size k, we convert it
to an instance of Dominating Set as follows:
For each edge e = (u,v) in the graph G, we add a vertex suv and the edges (u,suv)
and (v,suv). Thus we create a ”triangle” on each edge of G. Call this new graph G’ =
(V’,E’).
Take the figure above as example, Vertex Cover in G would be {u,x}, and which is also a Dominating Set in G’ (from construction earlier). Note that, however, {u,v} in G is a Dominating Set, but not a Vertex Cover.
Claim 4.13.3.1. Vertex Cover ≤p Dominating Set(Vertex Cover is a special case of
Dominating Set)
G has a vertex cover of size at most k if and only if G’ has a dominating set of
size at most k.
G has a vertex cover of size at most k ⇒ G’ has a dominating set of size at most k.
Proof. Let C be a vertex cover in G with size k. Because every edge in G is incident to some vertex in C, it is seen that the original vertices of G which are in G’ are dominated by those very same vertices in C. For every edge e = (u,v) either v or w is in C. This means that the vertex suv in G’ is dominated by C. So all the new vertices in G’ are also dominated, and C is a dominating set for G’ __
G’ has a dominating set of size at most k ⇒ G has a vertex cover of size at most k.
Proof. Let D be a dominating set of size K in G’. There can be two cases: Either D contains only vertices from the original G or some new vertices from G’ are also in D. In the first case all the new vertices (representing an edge) have an edge to a vertex in D. This means that D covers all edges and is a valid vertex cover set for G. However, if there are any new vertices in D, they need to be replaced by a vertex from G: A new vertex suv in D needs to be replaced by u or v. In either case the edge e = (u,v) will be covered by D. If u or v already is in D they need not be added. After all the new edges have been removed, D will be a valid vertex cover for G __
