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 ε > 0, if an instance of the Min-CVCB problem has a minimum vertex cover of size (k_u, k_l), our algorithm constructs a vertex cover of size (k_u~*, k_l~*), satisfying xnax{k_u~*/k_u, k_l~*/k_l} ≤ 1 + ε.