Research

Research at the chair is centred around the design of efficient algorithms (with guarantees) for discrete structures, with a particular interest in the interplay between efficiency and the combinatorial structure of the input instances.

For example, many classical problems on graphs are NP-hard in general, but they lie at the core of numerous applications, so they need to be solved in practice. These problems include the famous Graph Colouring Problem, the Hamiltonian Cycle Problem, and many others. However, if we restrict the inputs to trees or "tree-like" graphs, many of these problems become efficiently solvable.
 
We aim to push the boundaries of efficient solvability, with new algorithms tailored to the structure of the input instances, and complementing the picture by proving lower bounds. We are interested in classical and modern algorithms, such as parameterised algorithms, sublinear time algorithms, and property testing.

Beyond Algorithms and Complexity Theory, our research draws from the areas of Graph Theory, Logic and Combinatorics, Algorithmic Model Theory, and many more.   

Our research has applications in a wide range of areas beyond graphs and networks, including database query evaluation, model checking and verification, combinatorial games, compiler construction, and AI.