Algorithms and Complexity

Algorithms group

Theoretical Computer Science forms the foundations of computing. One of its primary aims is to provide a mathematically grounded theory for developing sophisticated algorithms for real-world problems. This includes mathematical modelling of algorithmic approaches, estimation of the complexity of computational problems, and understanding the limits of efficient computation through computational complexity.

Our research

The Algorithms and Complexity theme is led by Kristina Vušković. Research within the theme includes graph theory, algorithms on graphs and discrete structures, the computational complexity of problems on discrete structures, logic and proof complexity, deterministic scheduling theory and its applications, randomised algorithms, probabilistic analysis of algorithms, approximation algorithms and combinatorial optimisation.

The research interests of the individual members include:

  • Isolder Adler: Structure of graphs and hypergraphs, logic and model theory, (parameterised) complexity theory, database theory, combinatorial games, theory of "big data".
  • Olaf Beyersdorff: Computational complexity, propositional proof complexity, satisfiability problems, bounded arithmetic, non-classical logics.
  • Martin Dyer: Sampling and counting, randomised algorithms, Markov chains, complexity theory, constraint satisfaction problems, random structures, probabilistic analysis, combinatorial optimisation.
  • Raymond Kwan: Public transport scheduling, integer linear programming, heuristics, meta-heuristics, hyper-heuristics. The research has led to Tracsis Plc, a Leeds University spin-out company.
  • Haiko Muller: Algorithms on graphs and partially ordered sets, fixed parameter algorithms, approximation algorithms, graph theory, special classes of graphs, width parameters of graphs.
  • Natasha Shakhlevich: Deterministic scheduling theory, scheduling with controllable parameters, scheduling algorithms for distributed computing. 
  • Kristina Vušković: Structural graph theory with algorithmic consequences.

We also have a large and lively group of postgraduate research students and postdoctoral fellows. We have been very successful in obtaining support from EPSRC and other funders and maintain a high number of international research collaborations.

View publications.

Research seminars

Jointly with the School of Mathematics, we organise the Algorithms, Logic, and Algebra seminars

PhD opportunities

We have opportunities for prospective PhD students including a number of studentships. This list is by no means definitive and you should feel free to contact the group to discuss your own interests. However, applicants should note that the research is inherently mathematical, and requires a background and interest in mathematics and/or the mathematical aspects of computer science.

Contact us

If you are interested in collaborating with us or joining our research team, please contact Professor Kristina Vušković.

View all members of the Algorithms and Complexity group.

Current grants

A New Dawn of Intuitionism: Mathematical and Philosophical Advances
PIs: Professor Michael Rathjen and Professor Olaf Beyersdorff
John Templeton Foundation, 2017-2020

Structure of Hereditary Graph Classes and Its Algorithmic Consequences (2016-2019)
PI: Professor Kristina Vušković
Funder: EPSRC (EP/N019660/1)

Randomized algorithms for computer networks (2014-2017)
PI: Professor Martin Dyer
Funder: EPSRC (EP/M004953/1)

Train unit scheduling optimisation (2015-2018)
PI: Dr Raymond Kwan
Funder: EPSRC (EP/M007243/1)

Train unit scheduling optimisation (2014-2018)
PI: Dr Raymond Kwan
Sponsor: First Rail Holdings Ltd

Correctness by Construction (2014-2017)
Coordinator: Professor Olaf Beyersdorff
Funder: EU, Marie Curie International Research Staff Exchange Scheme

Historic grants

Algorithms for Perfect Graphs and Other Hereditary Graph Classes (2013-15)
PI: Professor Kristina Vušković
Funder: EPSRC grant (EP/K016423/1)

Combinatorial Optimization Algorithms for Hereditary Graph Classes, (2010-12)
PI: Professor Kristina Vušković
Funder: EPSRC grant (EP/H021426/1)

Decompositions and Algorithms, (2005-08)
PI: Professor Kristina Vušković
Funder: EPSRC grant (EP/C518225/1)

Graph Decompositions and Perfect Graphs, (2001-05)
PI: Professor Kristina Vušković
Funder: EPSRC grant (GR/R35629/01)

Graph Structure Theory and Algorithmic Applications (2011-2016)
PI: Dr Isolde Alder
Funder: German Research Council