[DMANET] PhD Studentship in Algorithmic Graph Theory [Deadline extended to 6th April]

The School of Computing at Newcastle University is advertising a PhD studentship on Algorithmic Graph Theory supervised by Dr Konrad Dabrowski.

Application deadline: 6th April 2022
Start Date: September 2022
Award Duration: 3.5 years
Award Summary: 100% of home tuition fees paid, a £1,000 annual research budget and annual stipend of £15,609.

Project description: This project studies classes of graphs both from a structural and an algorithmic point of view. From a structural perspective, the aim is to classify which classes have certain desirable properties, such as having bounded clique-width or being well-quasi-ordered. From an algorithmic perspective, the aim is to study computationally hard problems to systematically pinpoint exactly what type of structure makes such problems easy or hard (both from a classical complexity and a parameterized point of view).

The project tries to do this for many problems simultaneously by using the underlying structure rather than trying to solve problems in an ad hoc way.

As an extreme example, if we consider graphs that have bounded clique and independence number, Ramsey's Theorem tells us that such graphs have bounded size, so computational problems can be solved on them in polynomial (even constant) time. How far can we relax such a condition and maintain the property that large classes of problems are still polynomial-time solvable?

There is scope in the project to study discrete structures more from the perspective of fundamental computer science or more from a mathematical perspective, depending on the candidate's interests.

Eligibility Criteria: You must have, or expect to achieve, at least a 2:1 Honours degree in an appropriate subject e.g. Mathematics or Computer Science and are expected to have excellent mathematical skills as well as an interest in discrete mathematics and/or algorithms. The award is available to applicants with a UK Home fee status only.

How To Apply: Please contact Dr Konrad Dabrowski at konrad.dabrowski@newcastle.ac.uk before making an application. You should include all application documents and write "PhD Studentship in Algorithmic Graph Theory" in the subject line. Suitable candidates will be invited to make an official application in the online portal.

Further details: https://www.ncl.ac.uk/postgraduate/fees-funding/search-funding/?code=comp2115
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************