The simple, little and slow things count: on parameterized counting complexity

Abstract

This contribution is intended to be a self-contained and minimally technical
exposition of the material in my 2015 dissertation, which was supervised
by Markus Bläser. As its title suggests, the thesis investigates the
complexity of combinatorial counting problems in the frameworks of parameterized
(and exponential-time) complexity. More precisely, the following
specific settings are explored:
Counting perfect matchings in structurally “simple” graphs, for instance,
in graphs that exclude specific fixed minors
Counting small subgraph patterns in large host graphs
Exponential lower bounds on the running time needed to solve counting
problems, assuming popular conjectures such as the exponentialtime
hypothesis