So essentially you are talking about Dominating Set. This problem is NP complete if you want to find dominating set of minimum cardinality even for bipartite graphs but you have some approximation algorithm to solve this problem. One can be found here.

A very good book for NP-completeness is "Garey and Johnson, Computers and Intractability: a guide to the theory of NP-completeness, 1979.".

Your problem about covering vertices (in an arbirary graph, not necessarily bipartite) is called "The MINIMUM DOMINATING SET problem" (http://en.wikipedia.org/wiki/Dominating_set). Nevertheless, one of the tipical reductions from SAT (satisfiability problem) already produces bipartite graphs. So, this problem is NP-hard even for bipartite graphs. The decisional version of MINIMUM DOMINATING SET, called DOMINATING SET, receives a graph G and a natural number k as input, and questions whether one can choose k vertices of G such that any other vertex is covered by the chosen ones.

The reduction works as follows. Consider an input of the SAT problem, i.e. a logical propositional formula consisting of a conjunction of disjunctions of literals (for example ((x1 or not(x2) or x3) and (not(x1) or x2 or x3) and ...), that is, a formula of the form (c1 and c2 and c3 and ... and cm), where each ci is a disjunction of literals. Let x1,x2,...,xn be the variables involved in the formula. Note that each literal is either of the form xi, or not(x1). Recall that the question in SAT is whether the formula is satisfiable, i.e. if there is a true/false assignment to the variables such that the formula evaluates to true. We know that the SAT problem is NP-hard, and hence, we are not able to solve it in polynomial time. In order to prove that DOMINATING SET is also NP-hard, we need to polynomially transform any input of SAT (a formula F) into an input of DOMINATING SET (a graph G and a number k) by preserving the answer (F is satisfiable if and only if there is a dominating set of size k in G). This suffices to argue that we are not able to find a polynomial time algorithm for DOMINATING SET: if we could do that, then our polynomial transformation from SAT to DOMINATING SET would give us a polynomial time for SAT, a contradiction. We construct G and k from F as follows: k is just n. For each variable xi we have three vertices vxi, vnot(xi), vxi' and there are edjes between every two of those three vertices. For each disjunction ci we have a vertex vci. For each literal xj inside ci, there is an edge between vxj and vci. For each literal not(xj) in ci, there is an edge between vnot(xj) and vci. There are no more edges.

The above reduction accomplishes "F is satisfiable iff there is a dominating set of size k in G":

=>) Suppose there is an assignment A:variables->{true,false} that satisfies F. We construct a dominating set S of size k=n as follows. For each variable xi, if A(xi)=true, then the vertex vxi is in S. Otherwise, if A(xi)=false, then the vertex vnot(xi) is in S. There are no more vertices in S. This set is dominating because each disjunction ci is satisfied, and hence, each vci is connected to a vertex in S. Of course, all vxi,xnot(xi),vxi' are connected to a vertex in S, since either vxi or vnot(xi) is in S.

<=) Suppose that we have a dominating set S of size k=n in G. First of all, note that each vxi' is either in S, or one of the corresponding vxi or vnot(xi) is in S, since vxi' must be dominated. This implies that for each i, at least one of vxi,vnot(xi),vxi' is in S. But it should be exactly one, since i ranges from 1 to n, and the number of elements in S is k=n. Thus, no vci is in S. Moreover, we can assume that no vxi' is in S: otherwise, by removing vxi' from S and adding any of vxi or vnot(xi), we still have a dominating set. In conclusion, for each i from 1 to n, either vxi or vnot(xi) is in S, only one of both is in S, and there are no other kind of vertices in S. At this point, we define the assignment A:variables->{true,false} as A(xi)=true if vxi is in S, and as A(xi)=false if vnot(xi) is in S. The assignment satisfies all cj because each vcj is dominated by S.

Note that the transformation produces a bipartite graph.