We consider a generalization of the well‐known domination problem on graphs. The (soft) capacitated domination problem with demand constraints is to find a dominating set D of minimum cardinality satisfying both the capacity and demand constraints. The capacity constraint specifies that each vertex has a capacity that it can use to meet the demands of dominated vertices in its closed neighborhood, and the number of copies of each vertex allowed in D is unbounded. The demand constraint specifies the demand of each vertex in V to be met by the capacities of vertices in D dominating it. In this paper, we study the capacitated domination problem on trees from an algorithmic point of view. We present a linear time algorithm for the unsplittable demand model, and a pseudo‐polynomial time algorithm for the splittable demand model. In addition, we show that the capacitated domination problem on trees with splittable demand constraints is NP‐complete (even for its integer version) and provide a polynomial time approximation scheme (PTAS). We also give a primal‐dual approximation algorithm for the weighted capacitated domination problem with splittable demand constraints on general graphs.
