Abstract
The study of counting problems has become a classical subfield of computational complexity theory since Valiant's seminal paper introduced the complexity class #P and proved that counting perfect matchings is complete for this class. Since then, counting problems have been refined along various dimensions, including approximate counting, counting on restricted graph classes, and counting modulo a fixed number. In this talk, we consider some of the most recent refinements, namely, the parameterized complexity and the exponential-time complexity of counting problems.
First, we will consider various parameterizations of the problem of counting perfect matchings, together with lower bounds under the counting exponential-time hypotheses #ETH and #SETH.
Then we turn our attention to counting general subgraphs H in a host graph G, parameterized by the size of H. This gives rise to the problems #Sub(C) for fixed graph classes C: For inputs H and G, where H is from C, we wish to count H-copies in G. We show that #Sub(C) is either polynomial-time solvable or #W[1]-complete.
Finally, we present block interpolation, a general framework for proving lower bounds under #ETH. This gives tight lower bounds for counting (perfect) matchings, vertex-covers, evaluating the Tutte polynomial, and various other problems.