University of West London Featured PhD Programmes
Imperial College London Featured PhD Programmes
De Montfort University Featured PhD Programmes

Testing the limits of efficient algorithms for computationally hard problems

   School of Computer Science

This project is no longer listed on and may not be available.

Click here to search for PhD studentship opportunities
  Dr Rajesh Chitnis  No more applications being accepted  Funded PhD Project (UK Students Only)

Birmingham United Kingdom Computer Architectures Data Analysis Data Science Human Computer Interaction Machine Learning

About the Project

Designing efficient algorithms is at the very heart of computer science. Typically, the efficiency of an algorithm is determined by how much resource the algorithm consumes as a function of its input size. However, most interesting computational problems are NP-hard which means that (unless P=NP) there is no polynomial time algorithm for such problems. The paradigm of parameterized (FPT) algorithms identifies different parameters of the input, and aims to design algorithms whose running time is efficient when these parameters are bounded.

This project aims to obtain optimal algorithmic results for NP-hard graph problems on special graph classes such as planar graphs, bounded genus, minor-free, intersection graphs in Euclidean space, etc. Given the NP-hardness of a problem on general graphs, the question is how exactly does the algorithmic complexity of the problem change according to the topology of special graph classes? Positive algorithmic results can be viewed as an indication to impose this topology on the input graph in practice to ensure that we can run efficient algorithms, whereas lower bounds are an indication that we need to impose stronger topological structure if the goal is to be able to use efficient algorithms.

There are two main (complementary) parts of the project:

1. Algorithmic results: In this part of the project, the aim is to design efficient algorithms for NP-hard problems on special graph classes by exploiting the topological structure. This will involve designing new algorithmic techniques in addition to learning how to use existing techniques.

2. Lower Bounds: In this part of the project, the aim is to show conditional (on well-believed hypothesis from computational complexity) lower bounds which match the running time of the algorithms designed in Part 1.

In addition to problems from theoretical computer science, there is also the possibility to undertake this systematic analysis for graph-theoretic problems arising from other areas of computer science such as machine learning, bioinformatics, etc.

Eligibility: First or Upper Second Class Honours undergraduate degree and/or postgraduate degree with Distinction (or an international equivalent). We also consider applicants from diverse backgrounds that has provided them with equally rich relevant experience and knowledge. Full-time and part-time study modes are available.

We expect the student to have an undergraduate degree in Mathematics or Computer Science, and familiarity with graph theory & algorithms, theory of computation, discrete mathematics, writing proofs, etc. Programming experience is not necessary but would be helpful. During the course of the PhD project, the student will develop skills in algorithmic techniques (bidimensionality, dynamic programming, graph minor theory, etc.) and lower bound methodologies (parameterized reductions, NP-hardness). There will also be opportunities to develop skills in writing, presentation and teaching

If your first language is not English and you have not studied in an English-speaking country, you will have to provide an English language qualification.

We want our PhD student cohorts to reflect our diverse society. UoB is therefore committed to widening the diversity of our PhD student cohorts. UoB studentships are open to all and we particularly welcome applications from under-represented groups, including, but not limited to BAME, disabled and neuro-diverse candidates. We also welcome applications for part-time study.

Funding Notes

The position offered is for three and a half years full-time study. The value of the award is stipend; £15,285 pa; tuition fee: £4,407. Awards are usually incremented on 1 October each year.
Search Suggestions
Search suggestions

Based on your current searches we recommend the following search filters.