Logik in der Informatik Prof. Dr. Martin Grohe

Institut für Informatik

Counting Small Things is Sometimes Hard

Parameterized Counting Complexity aims at describing Counting Problems via methods from Parameterized Complexity Theory. Intuitively, this means in most cases that certain structures under consideration are assumed to be small. A theory of the intractability of these problems is still in its early stages. I will outline the basic complexity classes of this theory as defined by Flum and Grohe. Furthermore the hardness of some problems such as that of counting bipartite cliques and that of counting induced cycles in a graph will be discussed. As far as tractability is concerned, I will introduce a counting analog of the popular concept of kernelizations.