Daniel Paulusma

Daniel Paulusma is a Professor in the Department of Computer Science at Durham University, where he serves as Head of the Algorithms and Complexity research group (ACiD). He obtained his PhD and Master's degrees from the University of Twente in 2001 and 1997 respectively, and has been at Durham University since 2004, progressing from Lecturer (2004-2011) to Senior Lecturer (2011-2013), Reader (2013-2015), and finally to Professor in 2015. He previously served as Director of Research for the School of Engineering and Computing Sciences from 2014 to 2017.

Paulusma's research spans two main areas: structural and algorithmic graph theory, with a focus on computational complexity of graph problems under input restrictions; and cooperative game theory, particularly matching games related to kidney exchange. His work has resulted in numerous survey papers and significant contributions to the field. He has received several prestigious awards including the CIAC 2025 Best Paper Award, ISAAC 2024 and 2023 Best Paper Awards, and the Glover-Klingman Prize for his work on graph contractions.

His recent publications demonstrate a strong focus on complexity frameworks for forbidden subgraphs, matching cuts, graph coloring, and kidney exchange algorithms. The research shows a consistent pattern of exploring computational complexity within specific graph classes, particularly H-free graphs, and developing frameworks to classify problems based on graph structure constraints.

• CIAC 2025 Best Paper Award for "Atoms versus avoiding simplicial vertices"
• ISAAC 2024 Best Paper Award for "Complexity framework for forbidden subgraphs II: Edge subdivision and the \"H\"-graphs"
• ISAAC 2023 Best Paper Award for "Matching cuts in graphs of high girth and H-free graphs"
• Glover-Klingman Prize for "The Computational Complexity of Graph Contractions I, II"

Paulusma has successfully supervised numerous PhD students including Yilin Li, Tala Eagling-Vose, Xin Ye, Siani Smith, Giacomo Paesani, Anthony Stewart, Carl Feghali, Jian Song, and Pim van 't Hof. He has secured substantial research funding including grants from the Leverhulme Trust, EPSRC, and Royal Society for projects on graph coloring, kidney exchange algorithms, and network structure analysis. His current projects include "Algorithmic Meta-classifications for Graph Containment" (2025-2028) and "KidneyAlgo: New Algorithms for UK and International Kidney Exchange" (2023-2025).

As Head of the Algorithms and Complexity research group (ACiD), Paulusma leads a vibrant research team focused on theoretical computer science problems with applications in network analysis, optimization, and game theory. The group regularly organizes workshops and collaborates with international researchers in the field.