DMS-EPSRC - The Power of Graph Structure
Lead Research Organisation:
University of Leeds
Department Name: Sch of Computing
Abstract
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.
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.
Planned Impact
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.
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.
People |
ORCID iD |
| K Vuskovic (Principal Investigator) |
Publications
Abrishami T
(2024)
Induced subgraphs and tree decompositions II: Toward walls and their line graphs in graphs of bounded degree
in Journal of Combinatorial Theory B
Abrishami T
(2024)
Induced Subgraphs and Tree Decompositions VIII: Excluding a Forest in (Theta, Prism)-Free Graphs
in Combinatorica
Abrishami T
(2024)
Submodular Functions and Perfect Graphs
in Mathematics of Operations Research
Abrishami T
(2024)
Tree independence number I. (Even hole, diamond, pyramid)-free graphs
in Journal of Graph Theory
Abrishami T
(2022)
Induced subgraphs and tree decompositions I: Even-hole-free graphs with bounded degree have bounded treewidth
in Journal of Combinatorial Theory B
Abrishami T
(2024)
Submodular functions and perfect graphs
in Mathematics of Operations Research
Cook L
(2024)
Graphs with all holes the same length
in Journal of Combinatorial Theory, Series B
Cook L.
(2024)
Graphs with all holes the same length
in Journal of Combinatorial Theory B
J. Horsffield
Claw-free beta-perfect graphs
in to appear in Discrete Mathematics
| Description | Treewidth is a parameter that emerged from the study of minor-closed classes of graphs. It in some sense describes global structure of a graph, which can then lead to efficient algorithms for different computational problems. For example, if a class of graphs has bounded treewidth then a large number of hard problems can be solved on the class efficiently. The link between different width parameters and their algorithmic consequences has been an active research topic in the algorithms community. In the last three decades the structural graph theory community focused on hereditary graph classes, and a number of long standing open problems were settled through the decomposition method (e.g. The Strong Perfect Graph Theorem). This project was focused on bridging the research techniques of the two communities. A new general method, called the central bag method, was developed in the paper Induced subgraphs and tree decompositions I (JCTB 2022). This method allows us to go from decomposition theorems that describe the structure locally to describing the structure globally. Consequently this method was applied in analysis of a number of hereditary graph classes, obtaining efficient algorithms for them. This paper was followed by a series 17 more papers, where the central bag method is used to try to understand structural reasons for classes to have large width (Induced subgraphs and tree decompositions I-XVIII). This series of papers has in fact brought together researchers from algorithms and structural graph theory community, and has led to exciting new results and insights. In the paper Tree independence number I (JGT2024) we prove that a certain subclass of even-hole-free graphs has bounded tree independence number (i.e. it has a tree decomposition in which each bag has independence number bounded by some constant), which implies that the independent set problem can be solved efficiently for this class. The central bag method was a fundamental technique in this paper too, and four more papers that followed so far in this series (parts I-V). In the paper Submodular functions and perfect graphs (MOR2024) we give a polynomial time combinatorial algorithm for the independent set problem on a certain subclass of perfect graphs. We prove the existence of particular structure that reduces the calculation to well-known submodular function minimization algorithm. In the paper Graphs with all holes the same length (JCTB2024) we give a complete structural characterisation of the class of graphs in which all chordless cycles of length greater than 4 have the same length. This structure result has already been used to investigate different computational problems. In the paper Bisimplicial separators (JGT2024) we further investigate properties of separators that consist of union of fixed number of cliques. |
| Exploitation Route | By quickly disseminatin our findings, by giving talks at workshoops, conferences and seminars, we engage the scientific community with our work. This research is at the interface of structural graph theory and theoretical computer science, so we also contribute to disseminating findings between these communities. |
| Sectors | Digital/Communication/Information Technologies (including Software) Education |