EPSRC Reference: 
EP/K025090/1 
Title: 
Detecting Induced Graph Patterns 
Principal Investigator: 
Paulusma, Professor D 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Engineering and Computing Sciences 
Organisation: 
Durham, University of 
Scheme: 
Standard Research 
Starts: 
25 September 2013 
Ends: 
24 December 2016 
Value (£): 
363,442

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 
16 Jan 2013

EPSRC ICT Responsive Mode  Jan 2013

Announced


Summary on Grant Application Form 
A graph is a network consisting of nodes called vertices and links between those nodes called edges representing some relationship such as individuals that are connected to other individuals in a social network. Graphs are ubiquitous, not only in science and engineering but also in real life, as is the study of whether a given graph H appears as a pattern within another given graph G so that G can be transformed to H via a sequence of operations. For instance, can a social network G be compressed to a smaller (and easier to analyze) network H without destroying too much information? This example shows that the notion of appearing as a pattern depends upon the operations allowed when transforming G into H. We consider the following four elementary graph operations:
1. vertex deletions
2. edge deletions
3. edge contractions
4. vertex dissolutions.
A vertex deletion removes a vertex (and its adjacent edges) from the graph. An edge deletion removes an edge from the graph. An edge contraction removes the vertices u and v of the edge (u,v) from the graph and replaces them by a new vertex that is made adjacent to precisely those remaining vertices to which u or v was previously adjacent. A vertex dissolution is the removal of a vertex v from the graph with exactly two neighbours u and w followed by the inclusion of the edge (u,w).
Combining these four graph operations leads to ten essential graph containment relations. For example, a graph H is called a minor of a graph G if H can be obtained from G by a sequence of vertex deletions, edge deletions and edge contractions (and so also vertex dissolutions), whereas H is an induced minor of G if we do allow vertex deletions and edge contractions but no edge deletions. Each graph containment relation corresponds to a decision problem:
subject to the specified containment relation, does a graph G contain some graph H?
In order to answer this question we must design a socalled algorithm, which can be seen as a set of instructions, like a recipe for preparing a meal, but with the purpose to turn it into a computer program to solve the problem automatically. A crucial aspect is the running time, i.e., the time it will take the computer to solve the problem. However, it may well be possible that the problem falls into the category of discrete optimization problems for which no reasonably fast algorithm is known, and for which the existence of such an algorithm is even considered to be unlikely.
One of the most important and fundamental achievements of Theoretical Computer Science and Discrete Mathematics is Robertson and Seymour's Graph Minor Project. They have provided a structural characterization of graphs without a forbidden minor and have designed an algorithm that solves any problem HMinor in cubic time; the latter problem is to decide whether a given graph contains some fixed graph H (i.e., that is not part of the input) as a minor. Their theory has led to deep results across Computer Science and Mathematics. An important consequence of their theory is that any containment problem allowing edge deletions can be efficiently solved.
Our overarching aim is to develop a theory, similar to that of Robertson and Seymour, but on induced containment relations, i.e., when edge deletions are not permitted graph operations. As techniques that are useful for their noninduced counterparts can no longer be applied, a basic theory for induced containment relations, similar to the Graph Minor Project of Robertson and Seymour, is largely absent. Our research proposal aims to change this.

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: 
