Dominating set problem

From Wikipedia, the free encyclopedia

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

1 Definition
2 Example
3 NP-complete
- 3.1 Proof
- 3.2 Example
4 Approximation
5 References

[edit] 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.

[edit] Example

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

[edit] NP-complete

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

[edit] 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$ ) Let C be a vertex cover in G with size k. Because every edge in G is incident to some vertex in C, we can see that the original vertices of G which are in G ' are dominated by those very same vertices in C.

The new vertices in G ' which represent edges in G are also dominated, because every edge in G is covered by a vertex in C. Therefore, all of those vertices in G ' which represent edges are neighbors of a vertex of C. So, any vertex cover C for a graph G is also a dominating set for the graph G '.

[edit] Example

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

[edit] 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$

[edit] 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