  We study partial and budgeted versions of the well studied connected
dominating set problem. In the partial connected dominating set problem, we are
given an undirected graph G = (V,E) and an integer n', and the goal is to find
a minimum subset of vertices that induces a connected subgraph of G and
dominates at least n' vertices. We obtain the first polynomial time algorithm
with an O(\ln \Delta) approximation factor for this problem, thereby
significantly extending the results of Guha and Khuller (Algorithmica, Vol.
20(4), Pages 374-387, 1998) for the connected dominating set problem. We note
that none of the methods developed earlier can be applied directly to solve
this problem. In the budgeted connected dominating set problem, there is a
budget on the number of vertices we can select, and the goal is to dominate as
many vertices as possible. We obtain a (1/13)(1 - 1/e) approximation algorithm
for this problem. Finally, we show that our techniques extend to a more general
setting where the profit function associated with a subset of vertices is a
monotone "special" submodular function. This generalization captures the
connected dominating set problem with capacities and/or weighted profits as
special cases. This implies a O(\ln q) approximation (where q denotes the
quota) and an O(1) approximation algorithms for the partial and budgeted
versions of these problems. While the algorithms are simple, the results make a
surprising use of the greedy set cover framework in defining a useful profit
function.
