Structure of hereditary graph classes and its algorithmic consequences

Project description

Developing efficient algorithms for solving combinatorial optimization problems is of great importance to the modern technological society. Many diverse applications in the real world when modelled by graphs reduce to classical optimization problems such as optimally coloring the vertices of a graph (the chromatic number), or finding the size of a largest clique or a stable set. These problems are unfortunately NP-hard in general, but become polynomially solvable when restricted to different classes of graphs.

This project will focus on developing techniques for obtaining combinatorial optimization algorithms by exploiting structural properties of hereditary graph classes (i.e. classes closed under taking induced subgraphs). For a difficult optimization problem to be solved in polynomial time for a given class, it means that this class must have some strong structure. This research is about understanding structural reasons that enable the design of efficient algorithms, and developing techniques for obtaining the desired structure theorems and using them in algorithms. 

Entry requirements

Applications are invited from candidates with a minimum of a UK upper second class honours degree (2:1), and/ or a Master's degree in a relevant subject. We also recognise relevant industrial and academic experience.

How to apply

Formal applications for research degree study should be made online through the university's website. Please state clearly in the research information section of your application, the name of the PhD you wish to apply for is 'Structure of hereditary graph classes and its algorithmic consequences' as well as Professor Kristina Vušković as your proposed supervisor. In the funding section, please state 'School of Computing Funded Studentships' as your sponsor.

If English is not your first language, you must provide evidence that you meet the University’s minimum English Language requirements.

We welcome scholarship applications from all suitably-qualified candidates, but UK black and minority ethnic (BME) researchers are currently under-represented in our Postgraduate Research community, and we would therefore particularly encourage applications from UK BME candidates.  All scholarships will be awarded on the basis of merit.

If you require any further information please contact the Graduate School Office
e:, t: +44 (0)113 343 8000.