Dominating set problem

The dominating set problem is an NP-complete problem in graph theory.

Definition

An instance of the dominating set problem consists of:
* a graph "G" with a set "V" of vertices and a set "E" of edges, and
* a positive integer "K" smaller than or equal to the number of vertices in "G".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".

Example

In the graph at the right, the set {4,5} is an example of a dominating set of size two.

NP-complete

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.

Proof

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.

Let ("G", "K") be an instance of the vertex cover problem. Construct a new graph " G' " by adding new vertices and edges to the graph "G" as follows: For each edge ("v", "w") of "G", add a vertex "vw" and the edges ("v", "vw") and ("w", "vw") to " G' ". Furthermore, remove all vertices with no incident edges; such vertices would always have to go in a dominating set but are not needed in a vertex cover of "G". Overall, this transformation can be implemented in O(|"E"| + |"V"|) time (in big O notation), which is in particular polynomial time. An example is shown at right.

The claim that the dominating set problem is NP-complete now comes down to showing that "G"' has a dominating set "D" of size "K" if and only if "G" has a vertex cover "C" of size "k". This is done by proving the "if" ($Rightarrow$) and the "only if" ($Leftarrow$) parts separately.

($Rightarrow$) 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 "vw" in "D" needs to be replaced by "v" or "w". In either case the edge ("w","v") will be covered by "D". If "v" or "w" already is in "D" they need not be added. After all new edges have been removed "D" will be a valid vertex cover for "G". This proves the "if" part.

($Leftarrow$) 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 ("v","w") either "v" or "w" is in "C". This means that the vertex "vw" in "G' " is dominated by "C". So all the new vertices in "G' " are also dominated, and "C" is a dominating set for "G' ". This proves the "only if" part.

Restrictions

Also the connected dominating set problem is NP-complete for planar graphs.

Approximation

The optimization version of the algorithm, that is finding the smallest $|V\text{'}|$ such that $V\text{'}$ is a dominating set, is approximable. To be more precise, it is approximable within a factor of $1\; +\; log\; |V|$, but is not approximable within $c\; log\; |V|$ for some $c\; >\; 0$

Parameterized Complexity

Parameterized by K, the size of the dominating set sought for, the problem is [Parameterized_complexity_classes|W [2] -complete] , and thus is believed not to be fixed parameter tractable(fpt). Parameterized by the treewidth of the input graph G, the problem is fpt, with a running time $O(4^\{K\}cdot\; |V|)$ .

References

* A1.1: GT2, pg.190.
* Mitchell, S., and S. Hedetniemi [1977] , "Edge domination in trees", "Proceedings of the 8th Southeastern Conference on Combinatorics, Graph Theory, and Computing", Utilitas Mathematica Publishing, Winnipeg, 489-509.
* Yannakakis, M. and F. Gavril [1978] , "Edge dominating sets in graphs", unpublished manuscript.
* [http://www.nada.kth.se/~viggo/wwwcompendium/node11.html A compendium of NP optimization problems]