# Finding Perfect Matchings in Bipartite Hypergraphs

arXiv: https://arxiv.org/abs/1509.07007 · HTML: https://mlsanity.com/paper/1509.07007/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2015.

## Built on by (most cited first, 2 of 2)

- [NeuralQP: A General Hypergraph-based Optimization Framework for Large-scale QCQPs](https://mlsanity.com/paper/2410.03720/) (2024)
- [The CAT SET on the MAT: Cross Attention for Set Matching in Bipartite Hypergraphs](https://mlsanity.com/paper/2111.00243/) (2021)

## Abstract (arXiv)

Haxell's condition is a natural hypergraph analog of Hall's condition, which is a well-known necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell's condition holds it forces the existence of a perfect matching in the bipartite hypergraph. Unlike in graphs, however, there is no known polynomial time algorithm to find the hypergraph perfect matching that is guaranteed to exist when Haxell's condition is satisfied. We prove the existence of an efficient algorithm to find perfect matchings in bipartite hypergraphs whenever a stronger version of Haxell's condition holds. Our algorithm can be seen as a generalization of the classical Hungarian algorithm for finding perfect matchings in bipartite graphs. The techniques we use to achieve this result could be of use more generally in other combinatorial problems on hypergraphs where disjointness structure is crucial, e.g. Set Packing.