Parameterized Complexity for Approximate Counting and Enumeration

Lead Research Organisation: University of Oxford
Department Name: Computer Science

Abstract

This project falls within the EPSRC Information and Communication Technologies research area. The relevant research area is Theoretical Computer Science, and it also comes under the Mathematical Sciences research area but to a lesser extent.

The study of counting problems is a major area of interest within complexity theory. Given that counting problems arise in a diverse range of areas from economics to statistical physics, this provides good motivation for fully understanding the complexity of such problems. Unfortunately, for the majority of interesting counting problems, it is not believed that efficient algorithms exist to be able to solve them exactly. In light of this fact, there are a number of different approaches we can take towards coping with this apparent computational difficulty, or understanding which relaxed versions of hard counting problems are in fact tractable. Within this research, we aim to focus on two such relaxations on hard counting problems, these being approximation and parameterization.

Recent work, such as that in [1], has taken canonical approximate counting problems such as #BIS, the problem of counting independent sets in bipartite graphs, and examined the robustness of it's complexity by considering a number of variations in several different settings including both exact and approximate counting and exact and approximate parameterized counting. This refined analysis has lead to a number of interesting and surprising results. An additional advantage, as is mentioned in [3] is that often where we are not able to exhaustively classify the complexity of certain problems in the classical setting, it may be the case that we are able to do so by considering instead a problem from a fixed-parameter perspective.

The broad aims of this research are to better understand which features make other key counting problems hard or efficiently solvable, both approximately and exactly, which might be done by taking a similar approach to that in [1]. Other problems of interest include, for example, counting h-colourings (also known as homomorphisms) and list-h-colourings in graphs. These are problems that have been well-studied in the classical setting as we can see in [2] where a trichotomy classification is obtained for the complexity of approximately counting list-h-colourings.

We aim to further analyse the problem of counting homomorphisms in the parameterized setting. We would like to determine whether there are useful parameterizations under which these problems can be efficiently solved, or whether the hardness of solving these problems is preserved even under certain parameterizations. Overall, as was done in the classical situation, we aim to discover whether a complete complexity classification of the problem is possible.

Recent work provides good motivation to study these problems, however the problems that we have mentioned have not yet been studied like this in a parameterized setting therefore investigating these questions will require new and novel techniques.


[1] R. Curticapean, H. Dell, F. Fomin, L.A. Goldberg, and J. Lapinskas. A fixed-parameter per-
spective on #BIS. arXiv preprint arXiv:1702.05543, 2017.

[2] M.R. Jerrum, A. Galanis, and L.A. Goldberg. A complexity trichotomy for approximately
counting list H-colourings. ACM Transactions on Computation Theory, 9(2):article no. 9,
2017.

[3] R. Curticapean. The simple, little and slow things count: on parameterized counting complexity. 2015.

Publications

10 25 50

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/S515541/1 01/10/2018 30/09/2022
2077563 Studentship EP/S515541/1 01/10/2018 30/09/2022 James Stewart