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

CREATORPéter Biró, Gergely Csáji, Ildikó Schlotter
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE125 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-08827

Browse the full library · About the Tower of Babel