Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms

Motivated by the research in reconfigurable memory array structures, this paper studies the complexity and algorithms for the constrained minimum vertex cover problem on bipartite graphs (MIN-CVCB) defined as follows: given a bipartite graph G = (V, E) with vertex bipartition V = U boolean OR L and two integers k(u) and k(l), decide whether there is a minimum vertex cover in G with at most k(u) vertices in U and at most k(l) vertices in L. It is proved in this paper that the MIN-CVCB problem is NP-complete. This answers a question posed by Hasan and Liu. A parameterized algorithm is developed for the problem, in which classical results in matching theory and recently developed techniques in parameterized computation theory are nicely combined and extended. The algorithm runs in time O(1.26(ku + kl) + (k(u) + k(l))\G\) and significantly improves previous algorithms for the problem. (C) 2003 Elsevier Inc. All rights reserved.