Algorithms and Computational Complexity
There exists a pair of polynomial-time L-reductions between the minimum dominating set problem and the set cover problem (Kann 1992, pp. 108–109). These reductions (see below) show that an efficient algorithm for the minimum dominating set problem would provide an efficient algorithm for the set cover problem and vice versa. Moreover, the reductions preserve the approximation ratio: for any α, a polynomial-time α-approximation algorithm for minimum dominating sets would provide a polynomial-time α-approximation algorithm for the set cover problem and vice versa.
The set cover problem is a well-known NP-hard problem – the decision version of set covering was one of Karp's 21 NP-complete problems, which were shown to be NP-complete already in 1972. Hence the reductions show that the dominating set problem is NP-hard as well.
The approximability of set covering is also well understood: a logarithmic approximation factor can be found by using a simple greedy algorithm, and finding a sublogarithmic approximation factor is NP-hard. More specifically, the greedy algorithm provides a factor 1 + log |V| approximation of a minimum dominating set, and Raz & Safra (1997) show that no algorithm can achieve an approximation factor better than c log |V| for some c > 0 unless P = NP.
Read more about this topic: Dominating Set
Famous quotes containing the word complexity:
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)