Search Results

Documents authored by Manlove, David

Document
DOI: 10.4230/LIPIcs.WG.2026.2
Optimal b-Colourings and Fall Colourings in H-Free Graphs

Authors: Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, David Manlove, Fabricio Mendoza Granada, and Daniël Paulusma

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract
In a colouring of a graph, a vertex is b-chromatic if it is adjacent to a vertex of every other colour. We consider four well-studied colouring problems: b-Chromatic Number, Tight b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number, which fit into a framework based on whether every colour class has (i) at least one b-chromatic vertex, (ii) exactly one b-chromatic vertex, or (iii) all of its vertices being b-chromatic. By combining known and new results, we fully classify the computational complexity of b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number in H-free graphs. For Tight b-Chromatic Number in H-free graphs, we develop a general technique to determine new graphs H, for which the problem is polynomial-time solvable, and we also determine new graphs H, for which the problem is still NP-complete. We show, for the first time, the existence of a graph H such that in H-free graphs, b-Chromatic Number is NP-hard, while Tight b-Chromatic Number is polynomial-time solvable.
Cite as

Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, David Manlove, Fabricio Mendoza Granada, and Daniël Paulusma. Optimal b-Colourings and Fall Colourings in H-Free Graphs. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.WG.2026.2,
  author =	{Ahn, Jungho and Eagling-Vose, Tala and Lucke, Felicia and Manlove, David and Mendoza Granada, Fabricio and Paulusma, Dani\"{e}l},
  title =	{{Optimal b-Colourings and Fall Colourings in H-Free Graphs}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{2:1--2:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.2},
  URN =		{urn:nbn:de:0030-drops-261685},
  doi =		{10.4230/LIPIcs.WG.2026.2},
  annote =	{Keywords: b-chromatic number, tight graph, fall achromatic number, fall chromatic number, H-free graph}
}
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
DOI: 10.4230/LIPIcs.SEA.2020.20
Algorithms for New Types of Fair Stable Matchings

Authors: Frances Cooper and David Manlove

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
We study the problem of finding "fair" stable matchings in the Stable Marriage problem with Incomplete lists (SMI). For an instance I of SMI there may be many stable matchings, providing significantly different outcomes for the sets of men and women. We introduce two new notions of fairness in SMI. Firstly, a regret-equal stable matching minimises the difference in ranks of a worst-off man and a worst-off woman, among all stable matchings. Secondly, a min-regret sum stable matching minimises the sum of ranks of a worst-off man and a worst-off woman, among all stable matchings. We present two new efficient algorithms to find stable matchings of these types. Firstly, the Regret-Equal Degree Iteration Algorithm finds a regret-equal stable matching in O(d₀ nm) time, where d₀ is the absolute difference in ranks between a worst-off man and a worst-off woman in the man-optimal stable matching, n is the number of men or women, and m is the total length of all preference lists. Secondly, the Min-Regret Sum Algorithm finds a min-regret sum stable matching in O(d_s m) time, where d_s is the difference in the ranks between a worst-off man in each of the woman-optimal and man-optimal stable matchings. Experiments to compare several types of fair optimal stable matchings were conducted and show that the Regret-Equal Degree Iteration Algorithm produces matchings that are competitive with respect to other fairness objectives. On the other hand, existing types of "fair" stable matchings did not provide as close an approximation to regret-equal stable matchings.
Cite as

Frances Cooper and David Manlove. Algorithms for New Types of Fair Stable Matchings. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 20:1-20:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.SEA.2020.20,
  author =	{Cooper, Frances and Manlove, David},
  title =	{{Algorithms for New Types of Fair Stable Matchings}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{20:1--20:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.20},
  URN =		{urn:nbn:de:0030-drops-120945},
  doi =		{10.4230/LIPIcs.SEA.2020.20},
  annote =	{Keywords: Stable marriage, Algorithms, Optimality, Fair stable matchings, Regret-equality, Min-regret sum}
}
Document
DOI: 10.4230/LIPIcs.SEA.2018.8
A 3/2-Approximation Algorithm for the Student-Project Allocation Problem

Authors: Frances Cooper and David Manlove

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract
The Student-Project Allocation problem with lecturer preferences over Students (SPA-S) comprises three sets of agents, namely students, projects and lecturers, where students have preferences over projects and lecturers have preferences over students. In this scenario we seek a stable matching, that is, an assignment of students to projects such that there is no student and lecturer who have an incentive to deviate from their assignee/s. We study SPA-ST, the extension of SPA-S in which the preference lists of students and lecturers need not be strictly ordered, and may contain ties. In this scenario, stable matchings may be of different sizes, and it is known that MAX SPA-ST, the problem of finding a maximum stable matching in SPA-ST, is NP-hard. We present a linear-time 3/2-approximation algorithm for MAX SPA-ST and an Integer Programming (IP) model to solve MAX SPA-ST optimally. We compare the approximation algorithm with the IP model experimentally using randomly-generated data. We find that the performance of the approximation algorithm easily surpassed the 3/2 bound, constructing a stable matching within 92% of optimal in all cases, with the percentage being far higher for many instances.
Cite as

Frances Cooper and David Manlove. A 3/2-Approximation Algorithm for the Student-Project Allocation Problem. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.SEA.2018.8,
  author =	{Cooper, Frances and Manlove, David},
  title =	{{A 3/2-Approximation Algorithm for the Student-Project Allocation Problem}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.8},
  URN =		{urn:nbn:de:0030-drops-89439},
  doi =		{10.4230/LIPIcs.SEA.2018.8},
  annote =	{Keywords: Matching problems, Approximation, Algorithms, Stability}
}
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