Approximation algorithm based on chain implication for constrained minimum vertex covers in bipartite graphs

The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem) is an important NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the technique of chain implication. For any given constant epsilon > 0, if an instance of the Min-CVCB problem has a minimum vertex cover of size (k(u), k(t)), our algorithm constructs a vertex cover of size (k(u)*, k(t)*), satisfying max {k(u)*/k(u), k(t)*/k(t)} <= 1 + epsilon.