Search Results

Documents authored by Biró, Péter

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.31
Stable Hypergraph Matching in Unimodular Hypergraphs

Authors: Péter Biró, Gergely Csáji, and Ildikó Schlotter

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
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.
Cite as

Péter Biró, Gergely Csáji, and Ildikó Schlotter. Stable Hypergraph Matching in Unimodular Hypergraphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{biro_et_al:LIPIcs.ICALP.2025.31,
  author =	{Bir\'{o}, P\'{e}ter and Cs\'{a}ji, Gergely and Schlotter, Ildik\'{o}},
  title =	{{Stable Hypergraph Matching in Unimodular Hypergraphs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{31:1--31:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.31},
  URN =		{urn:nbn:de:0030-drops-234086},
  doi =		{10.4230/LIPIcs.ICALP.2025.31},
  annote =	{Keywords: stable hypergraph matching, Scarf’s Lemma, unimodular hypergraphs, university dual admission}
}
Document
DOI: 10.4230/DagRep.11.6.124
Matching Under Preferences: Theory and Practice (Dagstuhl Seminar 21301)

Authors: Haris Aziz, Péter Biró, Tamás Fleiner, and Bettina Klaus

Published in: Dagstuhl Reports, Volume 11, Issue 6 (2021)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 21301 "Matching Under Preferences: Theory and Practice". The seminar featured a mixture of technical scientific talks, survey talks, open problem presentations, working group sessions, five-minute contributions ("rump session"), and a panel discussion. This was the first Dagstuhl seminar that was dedicated to matching under preferences.
Cite as

Haris Aziz, Péter Biró, Tamás Fleiner, and Bettina Klaus. Matching Under Preferences: Theory and Practice (Dagstuhl Seminar 21301). In Dagstuhl Reports, Volume 11, Issue 6, pp. 124-146, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{aziz_et_al:DagRep.11.6.124,
  author =	{Aziz, Haris and Bir\'{o}, P\'{e}ter and Fleiner, Tam\'{a}s and Klaus, Bettina},
  title =	{{Matching Under Preferences: Theory and Practice (Dagstuhl Seminar 21301)}},
  pages =	{124--146},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2021},
  volume =	{11},
  number =	{6},
  editor =	{Aziz, Haris and Bir\'{o}, P\'{e}ter and Fleiner, Tam\'{a}s and Klaus, Bettina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.6.124},
  URN =		{urn:nbn:de:0030-drops-155826},
  doi =		{10.4230/DagRep.11.6.124},
  annote =	{Keywords: market design, matching under preferences, matching with distributional constraints, organ exchange, stable matching}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact