Detecting Induced Graph Patterns

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 so-called 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 H-Minor 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 over-arching 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 non-induced 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.

There is an undoubted chain of events as regards the societal impact of research, with this chain stretching from the seeds of intellectual ideas all the way through to the fruition of the impact in some user domain. Each link in the chain is crucial in realising the potential of the original ideas and the eventual impact is often arrived at via a circuitous route. Consider the development of computability theory in the early part of the last century. Mathematicians were developing notions of computation and proving that certain problems could never, ever be solved by any computer that would ever be built; moreover, they were doing this before any computer had actually been built! At that time, these activities were just intellectual pursuits and their significance was beyond the imagination of everyone, yet this research has resulted in the real digital machines and modern-day technology that are now pervasive within and fundamental to all aspects of society. Moreover, the fanciful notions of computers and computation as developed by Turing and his contemporaries continue to inspire, both directly and indirectly, new ways of computing.

The research in this proposal is foundational in nature, and may not lead directly to impact (`in one hop'). Hence, our intentions are to positively influence and impact upon other research areas which themselves are much closer to the frontier of real impact. In what follows we describe the proposed target areas of our research.

1. Mesh partitioning
Mesh partitioning is required in finite-element and finite-volume applications (across engineering and the mathematical sciences) where the excessive size of a mesh or the drive to use a parallel computing platform means that a given mesh needs to be partitioned so that loads are balanced and data is `locally maximised'. Multilevel partitioning algorithms are useful and popular in this regard. Here, an initial graph is progressively reduced, via a series of graph contraction rules, so that a partition is refined, level by level, subject to local optimisations.

2. Mobile networks
In telecommunications networks, the design of the actual network is a complex, important and time-consuming process. Take, for example, an area divided into cells, each containing a base station. Groups of base stations are controlled by a base station controller, which has a fixed number of packet control units to which base stations must be assigned. When a user changes base station, a service interruption is much longer if the user is changing packet control units too. Hence, the goal is to minimize such changes yet still retain an even overall load. A multilevel partitioning approach, where base stations are iteratively clustered, can be used. This approach involves iteratively applying local operations to graphs to move from the initial graph (representing all base stations) to a target graph (within which bases stations have been clustered).

3. Graph drawing
Graph drawing is actively applied in, for example, bioinformatics (metabolic networks, protein-protein interaction), business informatics (business process models) and the social sciences and criminology (social networks, phone-call graphs). In graph drawing, the aim is to visually represent a graph in a suitable fashion. A multilevel approach has been applied to graph drawing whereby a graph is iteratively made coarser by grouping vertices into cluster-vertices so that when the graph is `coarse enough', it is drawn and the iterative process is `unfolded' to obtain a drawing of the original graph.

It is clear that there are existing links between the research within our proposal, which is essentially concerned with the algorithmic difficulty of transforming a source graph to a target graph via local operations, and the application areas listed above and the methods inherent in many of the proposed solutions within these application areas. Our intention is to explore and strengthen these links.