Capacitated domination faster than O(n2)O(2n)

In this paper we consider the Capacitated Dominating Set problem — a generalisation of the Dominating Set problem where each vertex v   is additionally equipped with a number c(v)c(v), which is the number of other vertices this vertex has the capacity to dominate. We provide an algorithm that solves Capacitated Dominating Set exactly in O(n1.89)O(1.89n) time and polynomial space. Despite the fact that the Capacitated Dominating Set problem is quite similar to the Dominating Set problem, we are not aware of any published algorithms solving this problem faster than the straightforward O⁎(n2)O⁎(2n) solution prior to this paper. This was stated as an open problem at Dagstuhl seminar 08431 in 2008 and IWPEC 2008.We also provide an exponential approximation scheme for Capacitated Dominating Set which is a trade-off between the time complexity and the approximation ratio of the algorithm.

► A capacitated dominating set problem is an extension of dominating set. ► Each vertex can dominate only a given number of vertices (its capacity). ► We present an O(n1.89)O(1.89n) algorithm for finding the smallest capacitated dominating set in a general graph. ► We also present an exponential approximation scheme for the problem.