Daniel Paulusma's Homepage
Contact
Professor, Head of the Algorithms and Complexity research group (ACiD)
Biography
I was an Assistant Professor at the University of Twente (2001-2004) where I obtained my PhD degree in 2001 and Master's degree in 1997. I moved to Durham in 2004, where I had positions as Lecturer
(2004-2011), Senior Lecturer (2011-2013) and Reader (2013-2015) before becoming Professor in 2015. I was Director of Research for the School of Engineering and Computing Sciences (2014-2017).
Research
My first main interest lies in structural and algorithmic graph theory. In particular I consider the computational complexity of graph problems under input restrictions.
I have written several survey papers on this topic:
-
V.B. Le, F. Lucke, D. Paulusma and B. Ries, Maximizing matching cuts, Encyclopedia of Optimization, to appear
doi.
-
K.K. Dabrowski, M. Johnson and D. Paulusma,
Clique-width for hereditary graph classes,
London Mathematical Society Lecture Note Series 456 (2019) 1-56
doi.
-
P.A. Golovach, M. Johnson, D. Paulusma and J. Song,
A survey on the computational complexity of colouring graphs with forbidden subgraphs,
Journal of Graph Theory 84 (2017) 331-363
doi.
-
D. Paulusma,
Open problems on graph coloring for special graph classes,
Proc. WG 2015,
Lecture Notes in Computer Science 9224 (2015) 16-30
doi.
My second main interest lies in cooperative game theory, in particular matching games related to kidney exchange; see also our latest survey paper:
-
M. Benedek, P. Biro, M. Johnson, D. Paulusma and X. Ye, The complexity of matching games: A survey, Journal of Artificial Intelligence Research 77 (2023) 459-485
doi.
Here is a full list of my papers;
see also my profiles on Google Scholar and dblp.
Preprints of many of my papers are available on arXiv; see here for a complete list of my preprints.
Grants
- Algorithmic Meta-classifications for Graph Containment, Leverhulme Trust RPG-2024-182, 2025-28, PI
- Modern Graph Width Parameters: from Structure to Algorithms, International Centre for Mathematical Sciences, Research in Groups Grant, 2025, CI
- KidneyAlgo: New Algorithms for UK and International Kidney Exchange, EPSRC EP/X01357X/1, Joint Project with
David Manlove (project EP/X013618/1), 2023-2025, PI
-
Network Alignment and Matching, DSTL, Project with 4colors Ltd, 2023-2024
-
Balancing International Kidney Exchange,
Leverhulme Trust RF-2022-607, Research Fellowship, 2022-23, PI
- Graph Colouring: from Structure to Algorithms,
Royal Society IES\R1\191223, International Exchanges Grant with Hans Bodlaender, 2019-2022, PI
- The Complexity of Promise Constraint Satisfaction, EPSRC EP/R034516/1, 2018-2022, CI
- Graph Homomorphisms, London Mathematical Society, Research in Pairs Grant with Pawel Rzazewski, 2018, PI
- ALGOUK - A Network for Algorithms and Complexity in the UK, EPSRC EP/R005613/1, 2017-2020, CI
- The Price of Connectivity II, London Mathematical Society, Research in Pairs Grant with Martin Milanic, 2017, CI
- Efficient Graph Colouring Algorithms via Input Restrictions, Leverhulme Trust RPG-2016-258, 2016-2021, PI
- Complexity Aspects of Matching Games, Short Term Scientific Mission, COST Action IC1205, with Peter Biro, 2016
- The Price of Connectivity, London Mathematical Society, Research in Pairs Grant with Martin Milanic, 2014, PI
- Graph Colouring for Special Graph Classes, London Mathematical Society, Computer Science Small Grant with Dieter Kratsch, 2014, CI
- Detecting Induced Graph Patterns, EPSRC EP/K025090/1, 2013-2016, PI
- Coping with NP-Hardness: Parameterized and Exact algorithms, Royal Society JP100692, Joint Project with Fedor Fomin, 2011-2014, PI
- Exploiting Network Structure to Obtain Faster Algorithms, Institute of Advanced Study, Durham University, Sir Derman Christopherson / Sir James Knott Foundation Fellowship, 2011
- Algorithmic Aspects of Graph Coloring, EPSRC EP/G043434/1, 2009-2013, PI
- Structural Vulnerability Measures for Networks and Graphs, EPSRC EP/F064551/1, 2009-2012, PI from 2011
- Algorithmic Aspects of On-line Graph Coloring, Royal Society JP090172, Joint Project with Jiri Fiala, 2009-2011, PI
- Exact Algorithms for NP-Hard Problems, EPSRC EP/D053633/1, 2006-2010, PI
Awards
- ISAAC 2023 Best Paper Award for the paper "Matching cuts in graphs of high girth and H-free graphs",
with Carl Feghali, Felicia Lucke and Bernard Ries (doi).
- Glover-Klingman Prize for the pair of papers "The Computational Complexity of Graph Contractions I, II", Networks, Volume 51, Issue 3, May 2008, pp. 178-189 (doi) and Volume 52, Issue 1, August 2008, pp. 32-56 (doi),
with Asaf Levin and Gerhard Woeginger
Research Associates
PhD Students
- Yilin Li
- Tala Eagling-Vose
- Xin Ye
- Siani Smith, PhD, 2022
- Giacomo Paesani, PhD, 2021
- Anthony Stewart, PhD, 2017
- Carl Feghali, PhD, 2016
- Jian Song, PhD, 2013
- Pim van 't Hof, PhD, 2010
Visiting Research Students
Editorial Work
Conference Activities
- WG, SC chair
- PCC 2025, Invited speaker
- Dagstuhl Seminar 25041, Organiser
- MATCH-UP 2024, PC member
- MFCS 2024, PC member
- CMID 2024, PC member
- Games and Graphs (ACiD Workshop) , Organiser
- IPEC 2023, PC member
- Liverpool Algorithms Days Invited speaker
- BGTC 2023, Invited speaker
- GWP 2023 (Satellite Workshop of ICALP 2023), Organiser
- WG 2023, PC chair
- CiE 2023, PC member
- STACS 2023, PC member
- SOFSEM 2023, PC member
- DIMAP Theory Day 2022, Invited speaker
- Dagstuhl Seminar 22481, Organiser
- GWP 2022 (Satellite Workshop of ICALP 2022), Organiser
- MFCS 2022, PC member
- GWP 2021 (Satellite Workshop of ICALP 2021), Organiser
- BCC 2021, Organiser
- Algorithmic Graph Theory (Minisymposium MS-ID54 of 8ECM), Organiser
- CiE 2020, PC member
- Algorithms UK 2019, Invited speaker
- WG 2019, PC member
- CiE 2019, PC chair, Organiser
- AAMAS 2019, SPC member
- BCTCS & ALGOUK 2019, Organiser
- BCC 2019, Invited speaker
- Dagstuhl Seminar 19271 Organiser
- SWAT 2018, PC member
- AAMAS 2018, SPC member
- IPEC 2018, PC member
- Cycles and Colourings 2017, Invited speaker
- CoopMAS 2017, PC member
- ATCAGC 2017, Organiser
- 100 Years of Matching Theory in Hungary, Invited speaker
- CoopMAS 2016, PC member
- AAIM 2016, PC member
- WG 2016, PC member
- CoopMAS 2015, PC member
- WG 2015, Invited speaker
- AGTAC 2015, PC member
- CoopMAS 2014, PC member
- AAIM 2014, PC member
- MFCS 2013, PC member
- CoopMAS 2013, PC member
- ACiD 2010, Organiser
- IWOCA 2009, PC member
- WG 2008, Organiser
- BCTCS 2008, Organiser
Teaching
In 2024-2025 I teach the following module:
Lecture materials are on ultra (local access only).
Links