Dominating set problem

From Wikipedia, the free encyclopedia

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

Contents 1 Definition 2 Example 3 NP-complete 3.1 Proof 3.2 Restrictions 4 Approximation 5 Parameterized Complexity 6 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. 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.

[edit] Example

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

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

[edit] 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" () and the "only if" () parts separately.

() 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 the new edges have been removed, D will be a valid vertex cover for G. This proves the "if" part.

() 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.

[edit] Restrictions

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

[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 clog | V | for some c > 0

[edit] Parameterized Complexity

Parameterized by K, the size of the dominating set sought for, the problem is 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 .

[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