Dominating set problem

From Wikipedia, the free encyclopedia

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

Contents

[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 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, {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. 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

Vertex cover and dominating set have the same problem format. The difference is that a dominating set covers vertices, while a vertex cover covers edges. So the transformation has to build a graph using vertices to represent the edges from the original graph. This is described in the next section.

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>. Also if there are any singleton vertices (vertices with no edges to them), remove those. Note that the singletons are removed, as they are not needed in a vertex cover set, but they would always have to go in a dominating set. The transformation needs O(|E| + |V|) time (in big O notation) to run. So the it can be done in polynomial time.


Now the following needs to be proven: 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.

[edit] Example

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

[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 O(4^{K}\cdot |V|) .

[edit] References

Languages