On the approximability and exact algorithms for vector domination and related problems in graphs

We consider two graph optimization problems called vector domination and total vector domination. In vector domination one seeks a small subset SS of vertices of a graph such that any vertex outside SS has a prescribed number of neighbors in SS. In total vector domination, the requirement is extended to all vertices of the graph. We prove that these problems (and several variants thereof) cannot be approximated to within a factor of clnnclnn, where cc is a suitable constant and nn is the number of the vertices, unless P=NP. We also show that two natural greedy strategies have approximation factors lnΔ+O(1)lnΔ+O(1), where ΔΔ is the maximum degree of the input graph. We also provide exact polynomial time algorithms for several classes of graphs. Our results extend, improve, and unify several results previously known in the literature.