Daniel Paulusma's Homepage

Research

• 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 2024 Best Paper Award for the paper "Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs" (doi), with Vadim Lozin, Barnaby Martin, Sukanya Pandey, Mark Siggers, Siani Smith and Erik Jan van Leeuwen.
• ISAAC 2023 Best Paper Award for the paper "Matching cuts in graphs of high girth and H-free graphs" (doi), with Carl Feghali, Felicia Lucke and Bernard Ries.
• 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