Search Results

Documents authored by Schlotter, Ildikó

Document
DOI: 10.4230/DagRep.15.8.29
Frontiers of Parameterized Algorithmics of Matching under Preferences (Dagstuhl Seminar 25342)

Authors: Jiehua Chen, Christine Cheng, David Manlove, Ildikó Schlotter, and Manuel Sorge

Published in: Dagstuhl Reports, Volume 15, Issue 8 (2026)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 25342 "Frontiers of Parameterized Algorithmics of Matching under Preferences", held from August 17-22, 2025. The seminar brought together researchers from the Matching Under Preferences (MATCH-UP) and Parameterized Complexity Theory (PCT) communities to systematically apply parameterized techniques to computationally hard matching problems. The program included tutorials on parameterized algorithmics, surveys on MATCH-UP complexity and structure of stable matchings, contributed talks, and intensive working group sessions that explored fundamental open problems. This seminar represents the first focused effort to comprehensively map the parameterized complexity landscape of matching markets, establishing frameworks for ongoing collaboration between these communities. The report presents abstracts of talks, tutorials, working groups, and open problems in alphabetical order by speaker.
Cite as

Jiehua Chen, Christine Cheng, David Manlove, Ildikó Schlotter, and Manuel Sorge. Frontiers of Parameterized Algorithmics of Matching under Preferences (Dagstuhl Seminar 25342). In Dagstuhl Reports, Volume 15, Issue 8, pp. 29-45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{chen_et_al:DagRep.15.8.29,
  author =	{Chen, Jiehua and Cheng, Christine and Manlove, David and Schlotter, Ildik\'{o} and Sorge, Manuel},
  title =	{{Frontiers of Parameterized Algorithmics of Matching under Preferences (Dagstuhl Seminar 25342)}},
  pages =	{29--45},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2026},
  volume =	{15},
  number =	{8},
  editor =	{Chen, Jiehua and Cheng, Christine and Manlove, David and Schlotter, Ildik\'{o} and Sorge, Manuel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.15.8.29},
  URN =		{urn:nbn:de:0030-drops-257744},
  doi =		{10.4230/DagRep.15.8.29},
  annote =	{Keywords: Algorithmic design and complexity analysis, Matching markets, Matching theory, Parameterizec complexity analysis}
}
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.SWAT.2024.30
Parameterized Complexity of Submodular Minimization Under Uncertainty

Authors: Naonori Kakimura and Ildikó Schlotter

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
This paper studies the computational complexity of a robust variant of a two-stage submodular minimization problem that we call Robust Submodular Minimizer. In this problem, we are given k submodular functions f_1,… ,f_k over a set family 2^V, which represent k possible scenarios in the future when we will need to find an optimal solution for one of these scenarios, i.e., a minimizer for one of the functions. The present task is to find a set X ⊆ V that is close to some optimal solution for each f_i in the sense that some minimizer of f_i can be obtained from X by adding/removing at most d elements for a given integer d ∈ ℕ. The main contribution of this paper is to provide a complete computational map of this problem with respect to parameters k and d, which reveals a tight complexity threshold for both parameters: - Robust Submodular Minimizer can be solved in polynomial time when k ≤ 2, but is NP-hard if k is a constant with k ≥ 3. - Robust Submodular Minimizer can be solved in polynomial time when d = 0, but is NP-hard if d is a constant with d ≥ 1. - Robust Submodular Minimizer is fixed-parameter tractable when parameterized by (k,d). We also show that if some submodular function f_i has a polynomial number of minimizers, then the problem becomes fixed-parameter tractable when parameterized by d. We remark that all our hardness results hold even if each submodular function is given by a cut function of a directed graph.
Cite as

Naonori Kakimura and Ildikó Schlotter. Parameterized Complexity of Submodular Minimization Under Uncertainty. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kakimura_et_al:LIPIcs.SWAT.2024.30,
  author =	{Kakimura, Naonori and Schlotter, Ildik\'{o}},
  title =	{{Parameterized Complexity of Submodular Minimization Under Uncertainty}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.30},
  URN =		{urn:nbn:de:0030-drops-200702},
  doi =		{10.4230/LIPIcs.SWAT.2024.30},
  annote =	{Keywords: Submodular minimization, optimization under uncertainty, parameterized complexity, cut function}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.57
Shortest Two Disjoint Paths in Conservative Graphs

Authors: Ildikó Schlotter

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph G = (V,E) with edge weights w:E → ℝ, two terminals s and t in G, find two internally vertex-disjoint paths between s and t with minimum total weight. As shown recently by Schlotter and Sebő (2022), this problem becomes NP-hard if edges can have negative weights, even if the weight function is conservative, i.e., there are no cycles in G with negative total weight. We propose a polynomial-time algorithm that solves the Shortest Two Disjoint Paths problem for conservative weights in the case when the negative-weight edges form a constant number of trees in G.
Cite as

Ildikó Schlotter. Shortest Two Disjoint Paths in Conservative Graphs. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 57:1-57:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{schlotter:LIPIcs.STACS.2024.57,
  author =	{Schlotter, Ildik\'{o}},
  title =	{{Shortest Two Disjoint Paths in Conservative Graphs}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{57:1--57:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.57},
  URN =		{urn:nbn:de:0030-drops-197678},
  doi =		{10.4230/LIPIcs.STACS.2024.57},
  annote =	{Keywords: Shortest paths, disjoint paths, conservative weights, graph algorithm}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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