Details of Grant 

EPSRC Reference:	EP/V002813/1
Title:	DMS-EPSRC - The Power of Graph Structure
Principal Investigator:	Vuskovic, Professor K
Other Investigators:
Researcher Co-Investigators:
Project Partners:	Princeton University
Department:	Sch of Computing
Organisation:	University of Leeds
Scheme:	Standard Research
Starts:	01 June 2021	Ends:	31 May 2024	Value (£):	430,010
EPSRC Research Topic Classifications:	Logic & Combinatorics
EPSRC Industrial Sector Classifications:	No relevance to Underpinning Sectors
Related Grants:
Panel History:	Panel Date Panel Name Outcome 31 Aug 2020 EPSRC Mathematical Sciences Prioritisation Panel September 2020 Announced
Summary on Grant Application Form
Graphs are mathematical objects used to model a variety of problems arising in diverse areas such as computer science, social science, transportation, telecommunication, molecular biology, industrial engineering, etc. The line of inquiry that guides our research is: what is the global difference between general graphs and graphs that do not contain a particular substructure? We focus on the following question: what algorithmic problems that are known to be hard (NP-hard, meaning that it is highly unlikely that there will ever be an efficient way to solve them by a computer) for general graphs can be solved efficiently (in polynomial time) if certain structural restrictions are placed on the input (more precisely: certain induced subgraphs are forbidden)? Understanding this phenomenon is a very interesting question, both in discrete mathematics and in theoretical computer science. In recent years powerful methods were developed in the theoretical computer science community to address this question. Our goal is to use our expertise in structural graph theory to augment and strengthen these methods, and apply them to several long-standing open problems.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website:	http://www.leeds.ac.uk