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

abstract

• 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 L and two integers ku and kl, decide whether there is a minimum vertex cover in G with at most ku vertices in U and at most kl 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.26ku+kl + (ku+kl)|G|) and significantly improves previous algorithms for the problem.

authors

• Chen, Jianer

published proceedings

• JOURNAL OF COMPUTER AND SYSTEM SCIENCES

author list (cited authors)

• Chen, H., & Kanj, I. A.

citation count

• 50

complete list of authors

• Chen, H||Kanj, IA

publication date

• December 2003

publisher

• Elsevier  Publisher

published in

• Journal of Computer and System Sciences  Journal

keywords

• Bipartite Graph
• Graph Matching
• Parameterized Computation
• Vertex Cover

Digital Object Identifier (DOI)

• 10.1016/j.jcss.2003.09.003

start page

• 833

end page

• 847

volume

• 67

issue

• 4

URL

• http%3A%2F%2Fdx.doi.org%2F10.1016%2Fj.jcss.2003.09.003