I was an Assistant Professor at the University of Twente (20012004) 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
(20042011), Senior Lecturer (20112013) and Reader (20132015) before becoming Professor in 2015. I was Director of Research for the School of Engineering and Computing Sciences (20142017).
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.

K.K. Dabrowski, M. Johnson and D. Paulusma,
Cliquewidth for hereditary graph classes,
London Mathematical Society Lecture Note Series 456 (2019) 156
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) 331363
doi.

D. Paulusma,
Open problems on graph coloring for special graph classes,
Proc. WG 2015,
Lecture Notes in Computer Science 9224 (2015) 1630
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) 459485
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
 Modern Graph Width Parameters: from Structure to Algorithms, International Centre for Mathematical Sciences, Research in Groups Grant, 2025, CI
 Algorithmic Metaclassifications for Graph Containment, Leverhulme Trust RPG2024182, 202427, PI
 KidneyAlgo: New Algorithms for UK and International Kidney Exchange, EPSRC EP/X01357X/1, Joint Project with
David Manlove (project EP/X013618/1), 20232025, PI

Network Alignment and Matching, DSTL, Project with 4colors Ltd, 20232024

Balancing International Kidney Exchange,
Leverhulme Trust RF2022607, Research Fellowship, 202223, PI
 Graph Colouring: from Structure to Algorithms,
Royal Society IES\R1\191223, International Exchanges Grant with Hans Bodlaender, 20192022, PI
 The Complexity of Promise Constraint Satisfaction, EPSRC EP/R034516/1, 20182022, 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, 20172020, 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 RPG2016258, 20162021, 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, 20132016, PI
 Coping with NPHardness: Parameterized and Exact algorithms, Royal Society JP100692, Joint Project with Fedor Fomin, 20112014, 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, 20092013, PI
 Structural Vulnerability Measures for Networks and Graphs, EPSRC EP/F064551/1, 20092012, PI from 2011
 Algorithmic Aspects of Online Graph Coloring, Royal Society JP090172, Joint Project with Jiri Fiala, 20092011, PI
 Exact Algorithms for NPHard Problems, EPSRC EP/D053633/1, 20062010, PI
Awards
 ISAAC 2023 Best Paper Award for the paper "Matching cuts in graphs of high girth and Hfree graphs",
with Carl Feghali, Felicia Lucke and Bernard Ries (doi).
 GloverKlingman Prize for the pair of papers "The Computational Complexity of Graph Contractions I, II", Networks, Volume 51, Issue 3, May 2008, pp. 178189 (doi) and Volume 52, Issue 1, August 2008, pp. 3256 (doi),
with Asaf Levin and Gerhard Woeginger
Research Associates
PhD Students
 Yilin Li
 Tala EaglingVose
 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
 MATCHUP 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 MSID54 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 20242025 I teach the following module:
Lecture materials are on ultra (local access only).
Links