In graph theory, a dominating set for a graph G is a subset D of its vertices, such that any vertex of G is in D, or has a neighbor in D. The domination number γ(G) is the number of vertices in a smallest dominating set for G.
The dominating set problem concerns testing whether γ(G) ≤ K for a given graph G and input K; it is a classical NP-complete decision problem in computational complexity theory.[1] Therefore it is believed that there may be no efficient algorithm that can compute γ(G) for all graphs G. However, there are efficient approximation algorithms, as well as efficient exact algorithms for certain graph classes.
Dominating sets are of practical interest in several areas. In wireless networking, dominating sets are used to find efficient routes within ad-hoc mobile networks. They have also been used in document summarization, and in designing secure systems for electrical grids.