A minimum dominating set is a dominating set of smallest size in a given graph. The size of a minimum dominating set is known as the domination number of the graph. A minimum dominating set is always a minimal dominating set, but the converse does not necessarily hold. Finding a minimum dominating set of a general graph is NP-complete, which can be shown by reduction from the vertex cover problem (Garey and Johnson 1983, Mertens 2024). This means that no polynomial-time algorithm exists to compute a minimum dominating set. The fastest known algorithm to find a minimum dominating set for a general graph with vertex count left bracketing bar G right bracketing bar has time complexity O(1.4969 left bracketing bar G right bracketing bar ) (van Rooij and Bodlaender 2011, Mertens 2024).

dominating set | domination number | domination polynomial | minimal dominating set