Constrained Minimum Vertex Cover In Bipartite Graphs

With the technical development of VLSI (very large scale integrated circuit), the constrained minimum vertex cover in bipartite graphs (shortly Min-CVCB) for re-configurable arrays has attracted considerable attention in the literature. An extensive list of paper has been published in the literature of IEEE and the annual conferences. The Min-CVCB problem has been proved to be NP-complete.At present, the best exact algorithm for the Min-CVCB problem's running time is bounded by O((k_u+k_l)|G|+1.26^ku_kl), in which k_u is the spare rows and k_l is the spare columns. Based on it, this paper provides a new exact algorithm for this problem. By deeply analyzing the bipartite graphs' structures and listing all the possible joint of the blocks whose weight is at least 3 in a case-by-case exhaustive manner, and then makes the best of chain implication and bounded search-trees technology to construct new recurrence relations; as to the block after branching, the paper uses a dynamic programming algorithm, which can be solved in polynomial time. The algorithm runs in time O((k_u+k_l)|G|+1.1892^ku+kl). Based on it, by making use of the parameter computation technology and graph theory, this paper studied an subexponential algorithm for the Min-CVCB problem. However, the algorithm needs further improvement and addition.Since heuristic algorithms were unable to provide solutions in scheduled time; while exact algorithm could get optimal solutions, but the time complexity is exponential. This paper proposes a polynomial time approximation algorithm which is based on chain implication to solve the Min-CVCB problem. For any given constantε＞0, if the instance of the Min-CVCB problem has a minimum vertex cover (k_u, k_l), the algorithm can get a constrained approximate minimum vertex cover (k_u*, k_l*) with approximation ratio max{k_u*/k_u, kl_*/k_l}≤1+ε. The running time of the algorithm is proved to be O((k_u+k_l)|G|+2^2/ε) Obviously, the approximate algorithm has great sense in theory and applications.