A polynomial algorithm for the extendability problem in bipartite graphs

Let G = [V,E] be a simple connected graph and let k be an integer such that 0 < k < \V\/2. G is said to be k-extendable if it contains a perfect matching and every matching of k edges extends to, i.e. is a subset of, a perfect matching. The extendability problem consists in finding the maximum value of k, denoted k(0), such that G is k-extendable. We give in this paper the first polynomial algorithm for the extendability problem when the graph is bipartite. Its complexity is O(m.mint (k(0)(3) + n, k(0).n)) where n and m designate the number of vertices and edges of the graph respectively. Furthermore, if a perfect matching or a special orientation of the edges are known then this algorithm can be run in parallel in O(k(0).log n) time using a polynomial number of processors on a concurrent-read concurrent-write PRAM machine. (C) 1998 Elsevier Science B.V.