# Mitarbeiterseminar Logik in der Informatik

Freitag, 23. Juni 2006, 11:15 Uhr

RUD 25, Raum 4.410
## Counting Small Things is Sometimes Hard

Marc Thurley

Humboldt-Universität zu Berlin

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.