  We consider two graph optimization problems called vector domination and
total vector domination. In vector domination one seeks a small subset S of
vertices of a graph such that any vertex outside S has a prescribed number of
neighbors in S. 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 clnn, where c is a
suitable constant and n is the number of the vertices, unless P = NP. We also
show that two natural greedy strategies have approximation factors ln D+O(1),
where D 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.
