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. In other words, we want to know if there is a subset D of V of size less than or equal to K such that every vertex not in D is joined to at least one member of D by an edge in E.

Example

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

NP-complete

The dominating set problem has been proven to be NP-complete by a reduction from the vertex cover problem.

Proof

Vertex cover and dominating set has the same problem format; the difference is that a dominating set covers vertices, while a vertex cover covers edges. So, find a way to build a graph using vertices to represent the edges from the original graph. Let's show how to build the graph to make the reduction from vertex cover to dominating set:

Let <G, k> be an instance of the vertex cover problem. Build a new graph G' adding new vertices and edges to the graph G. Specifically, for each edge <v, w> of G, add a vertex vw and the edges <v, vw> and <w,vw>. The new graph obtained is denoted by G' .

Now, the proof: G' has a dominating set D of size k if and only if G has a vertex cover C of size k.

( $\Rightarrow$ ) D is a dominating set of size k in G'. So, every edge hits some vertex in D. D is a vertex cover in G of size k.

( $\Leftarrow$ ) C is a vertex cover in G with size k, so new and old vertices dominated by k vertices.

Example

The graph on the right shows the construction of G' to make the reduction.

Approximation

The optimization version of the algorithm, that is finding the smallest $|V'|$ such that $V'$ 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$

References

Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. 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.
A compendium of NP optimization problems