Sampling in Hereditary Classes

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.

Graphs are used widely in practical problem solving. Therefore, is of great interest to both theoreticians and practitioners to determine graph classes in which problems become easy that are hard in the general case. Problems of counting and random generation occur in many areas of application, Statistics, Statistical Physics and Biology, for example. More widely, real-world computing often involves integration over many variables, so the complexity of multivariate integration is of great interest in all areas of scientific computation. Counting gives an idealised model of multivariate integration, so it is important to understand when it may be computationally feasible. Consequently, we believe the results of this project will be of use in many areas of application. We intend to develop and implement algorithms which will be practically useful, as well as theoretically interesting.

The goal of the project is to understand when counting and sampling problems on graphs and related finite structures may be tractable. The work is firmly based in theoretical computer science, but the beneficiaries of such research could be all users of computer algorithms. Improved understanding of computational problems leads to improved algorithmic techniques, and these lead to improved software, and this can result in economic and social benefits in practical applications. Better understanding can also flag up computational problems where fast algorithms are unlikely to exist, and more heuristic methods must be employed.

Our main avenues for disseminating our work will be through high-impact academic communications in journals and conference proceedings.

We wil employ a PDRA, who will be fully involved in the theoretical work, but will also implement and test the algorithms developed. If we see the potential for exploitation of this practical work, we will certainly follow up on it. We also expect the PDRA to take responsibility for developing the web resource at graphclasses.org, which is widely used by graph theorists internationally.

In order to expose the work to the wider graph theory community, we plan to host a meeting of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG) at Leeds during the lifetime of the project. Additionally, we will seek to arrange a Dagstuhl seminar around the topic of the grant, bringing together people from the graph theory and counting communities to study problems of mutual interest.