Algorithms for metric-based problems on graphs.

This project aims to address problems in graph theory and graph algorithms. <br /> <br /> A graph consists of a vertex set representing a set of objects and an edge set representing pairs of related objects. This versatility of graphs has enabled researchers from diverse areas of computer science to convert a real-world problem to a combinatorial optimisation problem on graphs. As most combinatorial optimisation problems are NP-hard, natural approaches have been to design fixed-parameter tractable algorithms or approximation algorithms. Studies of these two algorithmic paradigms have led to a deeper understanding of computability and gave rise to algorithmic meta-theorems & frameworks to solve combinatorial optimisation problems on graphs.<br /> <br /> 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.

<p>Some relevant papers are as follows:</p> <ol> <li>T. Nguyen, A. Scott, & P. Seymour, (2025). <a data-auth="NotApplicable" href="https://arxiv.org/abs/2501.09839" id="OWAcc07e3bc-bdce-1485-8ec9-7f6f59a695d2">Coarse tree-width.</a> arXiv preprint arXiv:2501.09839.</li> <li>D. Chakraborty, J. Chalopin, F. Foucaud, and Y. Vaxès. <a data-auth="NotApplicable" href="https://arxiv.org/abs/2301.00278" id="OWA5dbe56d7-239f-6888-8dce-9a1331676539">Isometric Path Complexity of Graphs</a>. In 48th International Symposium on Mathematical Foundations of Computer Science. 2023.</li> <li>D. Chakraborty, F. Foucaud, A. Hakanen: <a data-auth="NotApplicable" href="https://sciencespo.hal.science/CAP20-25/hal-04214541v1" id="OWA3a66c0d2-d753-8a33-8c72-1f72383772b5">Distance-Based Covering Problems for Graphs of Given Cyclomatic Number.</a> FCT 2023: 132-146</li> </ol>

<p>Formal applications for research degree study should be made online through the <a data-auth="NotApplicable" href="https://www.leeds.ac.uk/research-applying/doc/applying-research-degrees" id="OWA3941955e-dadb-5f3b-3b05-a7969b1d27e9">University's website</a>. Please state clearly in the Planned Course of Study section that you are applying for <em><strong>PHD Computer Science FT</strong></em> and in the research information section that the research degree you wish to be considered for is <em><strong>Algorithms for hard metric-based problems on graphs</strong></em> as well as <a data-auth="NotApplicable" href="https://eps.leeds.ac.uk/computing/staff/14032/dr-dibyayan-chakraborty" id="OWA33c71c89-69b5-2cfd-26cd-86c8695693fb">Dr. Dibyayan Chakraborty</a> as your proposed supervisor. Please state clearly in the Finance section that the funding source you are applying for is<strong> <em>School of Computer Science Studentship 2025/26</em></strong><em>.</em></p> <p>Applications will be considered after the closing date.  Potential applicants are strongly encouraged to contact the supervisors for an informal discussion before making a formal application.  We also advise that you apply at the earliest opportunity as the application and selection process may close early, should we receive a sufficient number of applications or a suitable candidate is appointed.</p> <p><strong>Please note that you must provide the following documents in support of your application by the closing date of Thursday 15 May 2025:</strong></p> <ul> <li>Full Transcripts of all degree study or if in the final year of study, full transcripts to date</li> <li>Personal Statement outlining your interest in the project</li> <li>CV</li> </ul> <p>If English is not your first language, you must provide evidence that you meet the University's minimum English language requirements (below).</p> <p><em>As an international research-intensive university, we welcome students from all walks of life and from across the world. We foster an inclusive environment where all can flourish and prosper, and we are proud of our strong commitment to student education. Across all Faculties we are dedicated to diversifying our community and we welcome the unique contributions that individuals can bring, and particularly encourage applications from, but not limited to Black, Asian, people who belong to a minority ethnic community, people who identify as LGBT+ and people with disabilities. Applicants will always be selected based on merit and ability</em></p>

Applicants to research degree programmes should normally have at least a first class or an upper second class British Bachelors Honours degree (or equivalent) in an appropriate discipline. The criteria for entry for some research degrees may be higher, for example, several faculties, also require a Masters degree. Applicants are advised to check with the relevant School prior to making an application. Applicants who are uncertain about the requirements for a particular research degree are advised to contact the School or Graduate School prior to making an application.

The minimum English language entry requirement for research postgraduate research study is an IELTS of 6.5 overall with at least 6.5 in writing and at least 6.0 in reading, listening and speaking) or equivalent. The test must be dated within two years of the start date of the course in order to be valid. Some schools and faculties have a higher requirement.

<p class="MsoNoSpacing" style="text-align:start; margin-bottom:24px">A highly competitive School of Computer Science Studentship 2025/26 providing the award of full academic fees, together with a tax-free maintenance grant of £20,780 per year for 3.5 years. There are no additional allowances for travel, research expenses, conference attendance or any other costs.</p> <p>You will be responsible for paying the overtime fee in full in your writing up/overtime year (£340 in Session 2025/26), but the scholarship maintenance allowance will continue to be paid for up to 6 months in the final year of award.</p> <p><strong>Important:</strong> Please note that that the award does <strong><em>not</em></strong> cover the costs associated with moving to the UK.  All such costs (<a href="https://www.leeds.ac.uk/international-visas-immigration/doc/applying-student-visa">visa, Immigration Health Surcharge</a>, flights etc) would have to be met by yourself, or you will need to find an alternative funding source.</p> <p>Please refer to the <a href="https://www.ukcisa.org.uk/">UKCISA</a> website for information regarding Fee Status for Non-UK Nationals.</p>

<p>For informal enquiries about this project, please contact Dr Dibyayan Chakraborty by email to <a href="mailto:D.chakraborty@leeds.ac.uk">D.chakraborty@leeds.ac.uk</a></p> <p>For further information about your application, please contact PGR Admissions by email to <a href="mailto:phd@engineering.leeds.ac.uk">phd@engineering.leeds.ac.uk</a></p>