The dominating set problem is an NP-complete problem in graph theory.
An instance of the dominating set problem consists of:
The problem is to determine whether there is a dominating set of size K or less for G. That is, we want to know if there is a subset D of V of size less than or equal to K such that every vertex in V-D is joined to at least one member of D by an edge in E.
In the graph at the right, the set {4,5} is an example of a dominati...
more
The dominating set problem is an NP-complete problem in graph theory.
An instance of the dominating set problem consists of:
The problem is to determine whether there is a dominating set of size K or less for G. That is, we want to know if there is a subset D of V of size less than or equal to K such that every vertex in V-D is joined to at least one member of D by an edge in E.
In the graph at the right, the set {4,5} is an example of a dominating set of size two.
The dominating set problem has been proven to be NP-complete by a reduction from the vertex cover problem. The reduction needs to take input for the vertex cover problem and transform it, so it can be solved as a dominating set problem.
The vertex cover and dominating set problems are stated similarly. The difference is that a dominating set covers vertices, while a vertex cover covers edges. Thus, the transformation has to build a new graph that has vertices representing the edges of the original graph, as described below....
less
