Rate My Professor Matthew Johnson

Professor Matthew Johnson is Professor of Computer Science and Head of the Department of Computer Science at Durham University. He is a member of the Algorithms and Complexity research group (ACiD) and the Networks research group (NESTID). His research specializations encompass algorithmic graph theory, combinatorial optimization, and combinatorial designs, with particular emphasis on combinatorial reconfiguration, graph partitioning, and graph theory. Johnson has made significant contributions to understanding the computational complexity of graph problems, including reconfiguration problems, transversals, feedback vertex sets, and coloring algorithms for restricted graph classes. He has collaborated extensively with researchers such as Daniel Paulusma, Konrad Dabrowski, and Hans Bodlaender on projects exploring forbidden subgraph frameworks and tractability in subcubic graphs.

Johnson's publication record includes over 50 papers on topics such as 'Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem' (2024), 'Edge Multiway Cut and Node Multiway Cut are Hard for Planar Subcubic Graphs' (2024), 'Computing Balanced Solutions for Large International Kidney Exchange Schemes when Cycle Length is Unbounded' (2024), 'Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs' (2023), 'Steiner Trees for Hereditary Graph Classes' (2021), 'Computing Weighted Subset Transversals in H-Free Graphs' (2021), 'Graph Isomorphism for (H1,H2)-Free Graphs: An Almost Complete Dichotomy' (2019), 'Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs' (2016), and 'Mixing 3-Colourings in Bipartite Graphs' (2007). He has obtained major grants, including the Leverhulme Trust Research Project Grant for 'Efficient Graph Colouring Algorithms Via Input Restrictions' (2016-2021), EPSRC grant for 'Structural Vulnerability Measures for Networks and Graphs' (2009-2012), EPSRC grant for 'Extending the Theory of Colour Graphs' (2007-2011), Marie Curie Initial Training Network SCALUS (2009-2013), and Nuffield Foundation grant 'A General Theory of Colour Graphs' (2005-2006). Johnson has supervised PhD students Giacomo Paesani (2021), Dan Thomas (2020), Anthony Stewart (2017), Ioannis Lignos (2016), Carl Feghali (2016), and Foad Lotfifar (2016), as well as current students David Fairbairn, Nina Klobas, and Xin Ye. He organized the 28th British Combinatorial Conference in 2021 and was formerly a member of AlgoUK.