EPSRC Reference: 
EP/S016562/1 
Title: 
Sampling in Hereditary Classes 
Principal Investigator: 
Muller, Dr H 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Sch of Computing 
Organisation: 
University of Leeds 
Scheme: 
Standard Research 
Starts: 
01 January 2019 
Ends: 
31 December 2021 
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 #Phard, and polynomial time approximable or NPhard.
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 linegraphs of hereditary classes. The linegraph 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 linegraphs 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 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: 
http://www.leeds.ac.uk 