Citizendia
Your Ad Here

The dominating set problem is an NP-complete problem in graph theory. In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties In Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects

Contents

Definition

An instance of the dominating set problem consists of:

The problem is to determine whether there is a dominating set of size K or less for G. In Graph theory, a dominating set for a graph G = (V E is a Subset V&prime of V such that every vertex 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.

Example

In the graph at the right, {4,5} is an example of a dominating set of size 2. In Graph theory, a dominating set for a graph G = (V E is a Subset V&prime of V such that every vertex

NP-complete

The dominating set problem has been proven to be NP-complete by a reduction from the vertex cover problem. In Computational complexity theory a polynomial-time reduction is a reduction which is computable by a Deterministic Turing machine in Polynomial time In Computer science, the vertex cover problem or node cover problem is an NP-complete problem and was one of Karp's 21 NP-complete problems. 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

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. In Mathematics and Computer science, a graph is the basic object of study in Graph theory. 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. In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments 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.

Example

The graph on the right shows the construction of G' to make the reduction. In Mathematics and Computer science, a graph is the basic object of study in Graph theory.

Restrictions

Also the connected dominating set problem is NP-complete for planar graphs. In Graph theory, a connected dominating set of a graph G = (VE is a set of vertices V'\subset V such that \ V' is a

Approximation

The optimization version of the algorithm, that is finding the smallest | V' | such that V' is a dominating set, is approximable. In Graph theory, a dominating set for a graph G = (V E is a Subset V&prime of V such that every vertex 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

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). In Computer science, parameterized complexity is a measure of complexity of problems with multiple input parameters Parameterized by the treewidth of the input graph G, the problem is fpt, with a running time O(4^{K}\cdot |V|) . In Graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to speed up solving certain problems on the original graph

References

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic