Stable Hypergraph Matching in Unimodular Hypergraphs
Péter Biró, Gergely Csáji, Ildikó Schlotter · 2025
Read Stable Hypergraph Matching in Unimodular Hypergraphs by Péter Biró, Gergely Csáji, Ildikó Schlotter (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-08827.txt.
Description
Peter Biro, Gergely Csaji, and Ildiko Schlotter study in 2025 when stable matchings in hypergraphs can be found fast, for a class with a clean matrix trait. A stable matching pairs agents so no group would rather re-match among themselves. A classic lemma plus a known result guarantee such a matching exists when the hypergraph is normal, and a fuller version exists for the clean class in view.
No fast method was known to find one, so the team maps where the task turns tractable. For layered hypergraphs and for path-like ones with small edges, they give fast methods, even for weighted versions with capacities in the path case. Hardness results fence the other side: tuning over stable matchings stays hard even in layered cases. A three-way admission case for students, schools, and firms is worked out as a use case.
Catalog record
| CREATOR | Péter Biró, Gergely Csáji, Ildikó Schlotter |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 125 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-08827