DROPS

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/LIPIcs.ESA.2024.14

Approximating Maximum-Size Properly Colored Forests

Authors: Yuhang Bai, Kristóf Bérczi, Gergely Csáji, and Tamás Schwarcz

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract

In the Properly Colored Spanning Tree problem, we are given an edge-colored undirected graph and the goal is to find a properly colored spanning tree. The problem is interesting not only from a graph coloring point of view, but is also closely related to the Degree Bounded Spanning Tree and (1,2)-Traveling Salesman problems. We propose an optimization version called Maximum-size Properly Colored Forest problem, which aims to find a properly colored forest with as many edges as possible. We consider the problem in different graph classes and for different numbers of colors, and present polynomial-time approximation algorithms as well as inapproximability results for these settings. We also consider the Maximum-size Properly Colored Tree problem asking for the maximum size of a properly colored tree not necessarily spanning all the vertices. We show that the optimum is significantly more difficult to approximate than in the forest case, and provide an approximation algorithm for complete multigraphs.

Cite as

Yuhang Bai, Kristóf Bérczi, Gergely Csáji, and Tamás Schwarcz. Approximating Maximum-Size Properly Colored Forests. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bai_et_al:LIPIcs.ESA.2024.14,
  author =	{Bai, Yuhang and B\'{e}rczi, Krist\'{o}f and Cs\'{a}ji, Gergely and Schwarcz, Tam\'{a}s},
  title =	{{Approximating Maximum-Size Properly Colored Forests}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.14},
  URN =		{urn:nbn:de:0030-drops-210858},
  doi =		{10.4230/LIPIcs.ESA.2024.14},
  annote =	{Keywords: Approximation algorithm, (1,2)-traveling salesman problem, Degree bounded spanning tree, Properly colored forest}
}

Search Results

Documents authored by Csáji, Gergely

Stable Hypergraph Matching in Unimodular Hypergraphs

Abstract

Cite as

Approximating Maximum-Size Properly Colored Forests

Abstract

Cite as

Thanks for your feedback!

Could not send message