Finding perfect matchings in bipartite hypergraphs (Q2416439): Difference between revisions

Matching is one of the most applicable areas of graph theory. Finding matching number of a graph or a perfect maching for a graph is a very hard problem in general. There are several algorithms to do these. To find an efficient algorithm to find a maximum matching in a bipartite graph is an important question for everyone working in related areas. When the Haxell's condition which is the hypergraph analog of well-known Hall's condition is satisfied, then it is known that there exists a perfect matching in the bipartite graph. But interestingly enough, for hypergraphs, there is no known efficient polynomial time algorithm to find such a matching. \par In this article, the author proves the existence of an efficient algorithm for finding a perfect matching in bipartite hypergraphs when a stronger version of Haxell's condition is satisfied. The algorithm given here is a generalization of the classical Hungarian algorithm to find perfect matchings in bipartite graphs.