Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers of a given bipartite graph. Equivalently, we obtain a polynomial delay algorithm for listing the anti-vertices of the perfect matching polytope of G. We also provide generation algorithms for other related problems, including d-factors in bipartite graphs, and perfect 2-matchings in general graphs. (C) 2006 Wiley Periodicals, Inc.