EPSRC Reference: 
EP/V007793/1 
Title: 
New Frontiers in Parameterizing Away from Triviality 
Principal Investigator: 
Maadapuzhi Sridharan, Dr R 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Computer Science 
Organisation: 
University of Warwick 
Scheme: 
New Investigator Award 
Starts: 
01 November 2020 
Ends: 
31 October 2023 
Value (£): 
264,598

EPSRC Research Topic Classifications: 
Fundamentals of Computing 


EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 
Panel Date  Panel Name  Outcome 
03 Aug 2020

EPSRC ICT Prioritisation Panel August 2020

Announced


Summary on Grant Application Form 
Graphs are a commonly used model of realworld systems. A graph has two types of elements: vertices and edges. The vertices represent individual components of a system and the edges represent links or relationships between these components. The ubiquity of graph models across various domains has led to the design and analysis of graph algorithms growing into a rich subarea of Computer Science and Discrete Mathematics. Unfortunately, many relevant graph problems that occur in practice are NPhard in theory (essentially implying that they are unlikely to have efficient algorithms). This motivates the search for special structure that makes the problem easy to solve on those inputs possessing such structure. In fact, there is a vast amount of research devoted to identifying specific families of graphs on which certain NPhard graph problems can be solved efficiently. Thus, if the given model happens to fall into any of these families (called graph classes), then one can solve various problems on it efficiently. Some wellknown graph classes are  complete graphs (each pair of vertices are linked by an edge), boundeddegree graphs (every vertex is linked to a small number of other vertices), lowdiameter graphs (every vertex can be reached from any vertex by following few edges).
Unfortunately, although networks observed in the real world have some structural characteristics that seem exploitable, they usually do not fall cleanly into rigidly defined graph classes obtained from theoretical models. But what if an observed network is not contained in a specific graph class, but resembles the graphs in this class, except for a few differences? Could one lift efficient algorithms that work on this graph class, to efficient algorithms for those graphs that are not contained within the classes, yet are still reasonably "close" to it? For example, suppose that we want to query for a smallest set of vertices that are cumulatively incident on all the edges in our graph. If our graph is a complete graph, then this query can be answered efficiently. But what if our graph is "close" to complete, that is, except for a few pairs of vertices, every other pair of vertices has an edge linking them? Could the same query still be answered efficiently? The answer turns out to be, yes!
Thus, in the last decade, there has been a systematic effort to lift efficient algorithms from graph classes to graphs close to the classes. A key challenge in this effort is to understand what "close" means. A common way of mathematically modelling the proximity of a graph to a graph class is via various notions of graph edit distance. These are simply the number of vertices and/or edges one needs to add/remove (called edit operations) in the given graph, to reach some graph in the graph class. These notions of graph edit distance have been instrumental in the design of efficient algorithms, especially in the active subarea of algorithmics called Parameterized Complexity.
This project aims to take a significant stride forward in this area by formally introducing new and more complex notions of graph edit distance and studying their impact on efficient solvability of NPhard problems. These notions of edit distance will depend not on the number of edit operations as they traditionally have, but on their inherent structure. The success of parameterized complexity has shown that studying the structure of relevant objects as opposed to only considering their size, can have a powerful impact on efficient solvability of computational problems. In summary, this project will lay the foundations for an advanced algorithmic theory built on "structural edit distances" between graphs, develop new algorithms for fundamental problems and uncover hitherto unknown efficiently solvable instances. The project deals with a fundamental research topic in algorithmics and will contribute towards major advances in this subarea of theoretical computer science.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic 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.warwick.ac.uk 