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

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 V′  of V of size less than or equal to K such that every vertex not in V′  is joined to at least one member of V′  by an edge in E.

NP-complete

The dominating set problem has been proven to be NP-complete by a reduction from the vertex cover problem.

References

• Garey, M. and D. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, 1979.
• 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.