Dominating set problem

	Email		Print
	Bookmark		Link

Dominating set problem

The dominating set problem is an NP-complete

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of problems having two properties:* Any given solution to the problem can be verified quickly ; the set of problems with this property is called NP ....
problem in graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graph : mathematical structures used to model pairwise relations between objects from a certain collection....
.
nstance of the dominating set problem consists of: The problem is to determine whether there is a dominating set

Dominating set

In graph theory, a dominating set for a Graph G = is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge....
of size K or less for G. That is, we want to know if there is a subset

Subset

In mathematics, especially in set theory, a Set A is a subset of a set B if A is "contained" inside B. Notice that A and B may coincide....
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.

he graph at the right, the set is an example of a dominating set

Dominating set

In graph theory, a dominating set for a Graph G = is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge....
of size two.

dominating set problem has been proven to be NP-complete by a reduction

Polynomial-time reduction

In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time....
from the vertex cover problem.

Discussion

Ask a question about 'Dominating set problem'

Start a new discussion about 'Dominating set problem'

Answer questions from other users

Full Discussion Forum

Encyclopedia

The dominating set problem is an NP-complete

NP-complete

Graph theory

In mathematics and computer science, graph theory is the study of graph : mathematical structures used to model pairwise relations between objects from a certain collection....
.

Definition

An instance of the dominating set problem consists of:

a graph
Graph (mathematics)

In mathematics a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges....
G with a set V of vertices and a set E of edges, and
a positive integer
Integer

The integers are natural numbers including 0 and their negative and non-negative numberss . They are numbers that can be written without a fractional or decimal component, and fall within the set ....
K smaller than or equal to the number of vertices in G.

The problem is to determine whether there is a dominating set

Dominating set

Subset

Example

In the graph at the right, the set is an example of a dominating set

Dominating set

In graph theory, a dominating set for a Graph G = is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge....
of size two.

NP-complete

The dominating set problem has been proven to be NP-complete by a reduction

Polynomial-time reduction

In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time....
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.

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

Graph (mathematics)

In mathematics a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges....
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

Big O notation

In mathematics, big O notation describes the asymptotic analysis of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions....
), which is in particular polynomial time

Polynomial time

In computational complexity theory, polynomial time refers to the computation time of a problem where the run time, , is no greater than a polynomial function of the problem size, n....
. 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.

Restrictions

Also the connected dominating set

Connected dominating set

In graph theory, a connected dominating set of a graph is a set of vertices such that# is a dominating set of G, and# the subgraph induced subgraph by is connected graph....
problem is NP-complete for planar graphs.

Approximation

The optimization version of the algorithm, that is finding the smallest such that is a dominating set

Dominating set

In graph theory, a dominating set for a Graph G = is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge....
, is approximable. To be more precise, it is approximable within a factor of , but is not approximable within for some

Parameterized Complexity

Parameterized

Parameterized complexity

In computer science, parameterized complexity is a measure of complexity of problems with multiple input parameters. The theory of parameterized complexity was developed in the 1990s by Rod Downey and Michael Fellows....
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 .