Algorithms for Metric-Based Problems on Graphs - School of Computer Science Studentship 2026/27

This PhD project at the University of Leeds aims to address problems in graph theory and graph algorithms. A graph consists of a vertex set representing a set of objects and an edge set representing pairs of related objects. The versatility of graphs has enabled researchers from diverse areas of computer science to convert real-world problems to combinatorial optimisation problems on graphs. As most combinatorial optimisation problems are NP-hard, natural approaches have been to design fixed-parameter tractable algorithms or approximation algorithms. The broad purpose of this project is to study the "distance-metric" of interesting graph classes, and propose efficient algorithms for related optimisation problems. The candidate must have done courses on advanced graph theory and algorithms. Research experience in structural/algorithmic graph theory will be advantageous. This is a highly competitive School of Computer Science Studentship providing the award of full academic fees, together with a tax-free maintenance grant for 3.5 years. The project is supervised by Dr. Dibyayan Chakraborty in the Algorithms and Complexity research group.