| EPSRC Reference: |
EP/S016562/1 |
| Title: |
Sampling in Hereditary Classes |
| Principal Investigator: |
Muller, Dr H |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Sch of Computing |
| Organisation: |
University of Leeds |
| Scheme: |
Standard Research |
| Starts: |
01 February 2019 |
Ends: |
31 January 2022 |
Value (£): |
507,341
|
| 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 |
|
04 Sep 2018
|
EPSRC ICT Prioritisation Panel September 2018
|
Announced
|
|
|
Summary on Grant Application Form |
The project proposes to bring together two previously distinct areas of fundamental research in algorithms and computational complexity: algorithms for random generation and approximate counting, and structural graph theory. Both have been the subject of intense study over the last thirty years, and major advances have been made, but the communities involved have had little interaction.
The central aim of the project is to use graph structure in particular classes to provide better and/or simpler algorithms for problems of (approximate) counting, or to show that these problems remain as hard as for general graphs. The approach is that of theoretical computer science, classifying problems as polynomial time computable or #P-hard, and polynomial time approximable or NP-hard.
The project developed from a study of a problem in Statistics, posed by Diaconis, Graham and Holmes. This reduces to computing the permanent of structured matrices. Though the problem was not stated this way, it concerned hereditary graph classes. These are graph classes in which every (vertex) induced subgraph of any graph in the class belongs to the class. These classes are the central objects of study in modern graph theory.
The motivation for considering hereditary graph classes is twofold. Counting problems have been studied mainly for general graphs. However, restricted classes are of practical interest, and problems that are intractable in general graphs may become tractable. Hereditary classes also guarantee the equivalence between random sampling and approximate counting.
The intention of this project is to examine problems of exact and approximate counting in suitable hereditary graph classes. A hereditary class can be characterised by a (possibly infinite) set of forbidden induced subgraphs. Chordal graphs are a well known class: the forbidden subgraphs are chordless cycles of length at least 4. Graphs with a given maximum degree bound form a hereditary class, with an obvious set of forbidden subgraphs. These classes, along with the (hereditary) class of planar graphs, have been most studied. However, there are many other interesting hereditary classes, motivated by applications. For example, chordal graphs represent matrices with a "perfect" ordering for solving linear equations by Gaussian elimination. Initially, we will focus on problems which can be viewed as counting graph homomorphisms, and try to identify classes where these problems are polynomial time solvable. We expect this to give rise to new and interesting graph classes.
We will also consider problems on line-graphs of hereditary classes. The line-graph L (G) of a graph G = (V, E) has vertex set E, and an edge between e and e' if they are incident at a vertex of G. For example, the line-graphs of all graphs form a hereditary class, and have a well known set of forbidden subgraphs. A matching of G is an independent set in L(G).
More generally, we will also consider constraint satisfaction problems (CSPs). These have been studied intensively in recent years, and much progress has been made on counting problems for general inputs. However, there is very little work on suitably restricted input classes. CSPs can be viewed as homomorphism problems, so we will generalise our work on graphs to this setting as far as possible. In particular, we will consider hypergraph problems.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic 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.leeds.ac.uk |