DMS-EPSRC - The Power of Graph Structure

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.

Developing efficient algorithms for solving combinatorial problems has been of great importance to the modern technological society. Many problems arising in diverse areas such as transportation, telecommunication, molecular biology, industrial engineering, etc., when modelled by graphs reduce to classical optimisation problems addressed in this proposal. The three optimisation problems that will be intensely studied as part of the proposed research are colouring (which has applications in, for example, frequency assignment in communication networks, scheduling, and memory allocation) and clique and stable set problems (with applications in, for example, bioinformatics, molecular biology, coding theory, computer vision, and scheduling).

Some concrete examples of possible applications of the results we have already obtained, as well as those we hope to obtain, include the following. There is a central NP-hard problem in statistics and machine learning known as the maximum a posteriori (MAP) estimation problem, which is the problem of finding the most likely scenario that fits a given set of observations. It turns out that this question can be phrased as finding a maximum stable set in a suitable graph. Thus, being able to efficiently find a maximum stable set in a variety of graph classes is a much sought after tool in the area of analysing large data sets. Another possible application is in the area of communications. A graph is used to describe a communication channel, and its Shannon capacity determines how many distinct words can be communicated in such a way that they are guaranteed not to be confused in the presence of noise. Here the largest size of a stable set gives a useful upper bound.

Obtaining efficient algorithms for these and other problems that will be considered, on hereditary graph classes necessarily involves advancements in their mathematical understanding. The main thrust of this research is theoretical, it develops techniques to handle problems that are at the edge of what is polynomial time solvable. Given that computational problems addressed in this proposal arise in a wide range of applications, there is a real need for this type of theoretical research to continue advancing at the frontier.

To ensure pathways to impact the PIs will follow their usual practice of conducting highest quality research on the questions that are at the focus of their own research communities, and of collaborating with colleagues from adjacent research communities to cross pollinate. The results will be disseminated through publications in high quality academic journals, presentations at conferences and workshops, as well as taking opportunities when they arise to reach broader audiences. The PIs are also involved in organisation of workshops that bring together researchers in combinatorics and algorithms. These are the main dissemination routs in this area. With the papers in this field being typically quite long, it usually takes a few years for a paper to go through the refereeing process and appear in a journal. Making preprints of papers available online before they are fully refereed, allows other researchers to promptly follow up on the research ideas developed. The PIs have an excellent record of quickly disseminating their results, and this practice will continue. The practice of writing survey articles that digest current knowledge will also continue. To facilitate faster transfer of knowledge, the PIs will also contribute to development of web resource graphclasses.org which is used by a wide research community.

The desired impact will also be achieved through training of young researchers that go on to pursue careers in both academia and industry.