The Centre is concerned with the study of various kinds of algorithms – parameterised, exact, randomised, heuristic and approximate – for problems arising in graph and hypergraph theory, constraint satisfaction, combinatorial optimisation, and their numerous applications.
Our current main focus is, from a theoretical perspective, in parameterised algorithms and computational complexity and, from the point of view of applications, in access control in information security.
Members
Collaborators
We have close collaborations with many researchers across the globe, including:
- Paul Balister (University of Memphis, USA)
- Joergen Bang-Jensen (Southern Denmark University)
- Stephen A. Cook (University of Toronto, Canada)
- Martin C. Cooper (University of Toulouse III, France)
- Michael Forbes (University of Illinois at Urbana Champaign, USA)
- Andrei Gagarin (Cardiff University, UK)
- Peter G. Jeavons (Oxford University, UK)
- Daniel Karapetyan (University of Essex, UK)
- Stefan Kratsch (HU Berlin, Germany)
- Tonnian Pitassi (University of Toronto, Canada)
- M.S. Ramanujan (University of Warwick, UK)
- Felix Reidl (Birkbeck University of London, UK)
- Amir Shpilka (Tel Aviv University, Israel)
- Angelika Steger (ETH Zurich, Switzerland)
- Yuefang Sun (Shaoxing University, China)
- Avi Wigderson (Institute of Advanced Studies, Princeton, USA)
- Anders Yeo (Southern Denmark University)
- Meirav Zehavi (Ben-Gurion University, Israel)
- Xiaoyan Zhang (Nanjing Normal University, China)
- Stanislav Zivny (Oxford University, UK)
Research strands
Design and Analysis of Algorithms
We are interested in various algorithms such as fixed-parameter, exact exponential, approximation and heuristic algorithms. We develop algorithms on graphs, digraphs and hypergraphs, for constraint satisfaction, combinatorial optimization and logic problems. In design and analysis of algorithms, we use graph-theoretical, combinatorial, algebraic, probabilistic and other methods.
For our publications, see personal webpages of members of the centre, dblp, or Google Scholar.
Computational Complexity
We are interested in classical and parameterized complexity, complexity of satisfiability, proof complexity, applications of logic in computer science, the interplay between algebra and computation, and the theory of SAT-solving.
For our publications, see personal webpages of members of the centre, dblp, or Google Scholar.
Graph Theory and Algorithms
We are interested in directed, undirected, random, weighted, signed and other types of graphs as well as their generalizations such as hypergraphs, hypertournaments and directed hypergraphs. We study structural properties of graphs, algorithms on graphs and applications of graphs.
A recent book "Classes of Directed Graphs" edited by J. Bang-Jensen and G. Gutin (Springer, 2018, in print) consists of chapters devoted to various important classes of directed graphs and written by experts in these classes of digraphs.
For our publications, see personal webpages of members of the centre, dblp, or Google Scholar.
Access Control in Information Security
We are interested in various access control problems. In particular, we have done significant research on the Workflow Satisfiability Problem (aka Constraint Satisfaction Problem in access control) designing efficient theoretical and practical algorithms to solve WSP and its generalization, the Bi-Objective WSP, which allows us to decide in cases when the WSP is unsatisfiable. We studied various constrains for WSP introducing a wide family of constraints, user-independent constraints, and resilience in WSP models. Our members received best papers awards at SACMAT 2015 and 2016 for WSP research.
For our publications, see personal webpages of members of the centre, dblp, or Google Scholar.
Constraint Satisfaction Problems
Constraint satisfaction problems arise in many areas. For example, the problems of scheduling a collection of tasks, or laying out a silicon chip, or interpreting a visual image, can all be formulated as CSPs. In any CSP there are variables which all have to be assigned values, subject to specified constraints. An equivalent way of defining CSPs is via homomorphisms between relational structures. We are interested understanding the computational complexity of constraint satisfaction problems, in particular, when CSPs and their generalizations (such as Valued CSPs) can be solved by efficient algorithms.
For our publications, see personal webpages of members of the centre, dblp, or Google Scholar.
Grants
Current
-
Gutin (PI), Cohen and Crampton (CoI's), Analyzing Security-aware Workflows, funded by the Leverhulme Trust, 2019 – 2021
Network for Algorithms and Complexity in the UK (AlgoUK), funded by EPSRC, 2017 – 2020
Past
since 2013
-
Cohen (PI), Constraint Network Tractability: Beyond Structure and Language, funded by EPSRC, 2014 – 17
-
Gerke (PI), LMS conference grants, 2013 and 2016
-
Gutin (PI), Cohen and Crampton (CoI's), Parameterized Algorithmics for the Analysis and Verification of Constrained Workflow Systems, funded by EPSRC, 2013 – 2016
-
Tzameret (PI), New Approaches to the Limits of Efficient Propositional Reasoning: Foundations, Algorithms and Approximations, funded by The National Natural Science Foundation of China, 2014 – 2017
-
Wahlstrom (PI), Polytope methods in parameterized complexity, funded by EPSRC, 2017 – 18.
