Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs

The constrained minimumvertex cover problem on bipartite graphs (the Min-CVCB problem) isan important NP-complete problem. This paper presents a polynomialtime approximation algorithm for the problem based on the techniqueof chain implication. For any given constant > 0, ifan instance of the Min-CVCB problem has a minimum vertex cover ofsize , our algorithm constructs a vertex cover of size, satisfying .