Die Suchmaschine für Unternehmensdaten in Europa
UK-Förderung (507.340 £): Probenahme in Erbklassen Ukri01.02.2019 Forschung und Innovation im Vereinigten Königreich, Großbritannien
Auf einen Blick
Text
Probenahme in Erbklassen
| Zusammenfassung | 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. |
| Kategorie | Research Grant |
| Referenz | EP/S016562/1 |
| Status | Closed |
| Laufzeit von | 01.02.2019 |
| Laufzeit bis | 31.07.2023 |
| Fördersumme | 507.340,00 £ |
| Quelle | https://gtr.ukri.org/projects?ref=EP%2FS016562%2F1 |
Beteiligte Organisationen
| University of Leeds | |
| Queen Mary University of London |
Die Bekanntmachung bezieht sich auf einen vergangenen Zeitpunkt, und spiegelt nicht notwendigerweise den heutigen Stand wider. Der aktuelle Stand wird auf folgender Seite wiedergegeben: University of Leeds, Leeds, Großbritannien.
Die Visualisierungen zu "University of Leeds - UK-Förderung (507.340 £): Probenahme in Erbklassen"
werden von
North Data
zur Weiterverwendung unter einer
Creative Commons Lizenz
zur Verfügung gestellt.
