2026-07-22T00:07:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23408 2025-10-02T12:54:20Z ddc:004 open_access

Stable Hypergraph Matching in Unimodular Hypergraphs Biró, Péter Csáji, Gergely Schlotter, Ildikó stable hypergraph matching Scarf’s Lemma unimodular hypergraphs university dual admission We study the NP-hard Stable Hypergraph Matching (SHM) problem and its generalization allowing capacities, the Stable Hypergraph b-Matching (SHbM) problem, and investigate their computational properties under various structural constraints. Our study is motivated by the fact that Scarf’s Lemma [Scarf, 1967] together with a result of Lovász [Lovász, 1972] guarantees the existence of a stable matching whenever the underlying hypergraph is normal. Furthermore, if the hypergraph is unimodular (i.e., its incidence matrix is totally unimodular), then even a stable b-matching is guaranteed to exist. However, no polynomial-time algorithm is known for finding a stable matching or b-matching in unimodular hypergraphs. We identify subclasses of unimodular hypergraphs where SHM and SHbM are tractable such as laminar hypergraphs or so-called subpath hypergraphs with bounded-size hyperedges; for the latter case, even a maximum-weight stable b-matching can be found efficiently. We complement our algorithms by showing that optimizing over stable matchings is NP-hard even in laminar hypergraphs. As a practically important special case of SHbM for unimodular hypergraphs, we investigate a tripartite stable matching problem with students, schools, and companies as agents, called the University Dual Admission problem, which models real-world scenarios in higher education admissions. Finally, we examine a superclass of subpath hypergraphs that are normal but not necessarily unimodular, namely subtree hypergraphs where hyperedges correspond to subtrees of a tree. We establish that for such hypergraphs, stable matchings can be found in polynomial time but, in the setting with capacities, finding a stable b-matching is NP-hard. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Péter Biró and Gergely Csáji and Ildikó Schlotter 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.31 urn:nbn:de:0030-drops-234086 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.31 eng https://creativecommons.org/licenses/by/4.0/legalcode