An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover

✍ Scribed by Henning Fernau; Rolf Niedermeier

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 382 KB
• Volume: 38
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2000.1141

✦ Synopsis

The constraint bipartite vertex cover problem (CBVC for short) is as follows: given a bipartite graph G with n vertices and two positive integers k 1 k 2 , is there a vertex cover taking at most k 1 vertices from one and at most k 2 vertices from the other vertex set of G? CBVC is NP-complete. It formalizes the spare allocation problem for reconfigurable arrays, an important problem from VLSI manufacturing. We provide a nontrivial so-called fixed parameter algorithm for CBVC, running in O 1 3999 k 1 +k 2 + k 1 + k 2 n time. Our algorithm is efficient and practical for small values of k 1 and k 2 , as occurring in applications. The analysis of the search tree is based on a novel bonus point system: after the processing of the search tree (which takes time exponential in k), a polynomial-time final analysis follows. Parts of the computation that would be normally done within the search-tree phase can be postponed; nevertheless, knowledge about the size of those parts can be used to reduce the length of the search paths (and hence the depth of the search tree as a whole) by a sort of bonus points.