Logik in der Informatik
Prof. Dr. Martin Grohe

Institut für Informatik

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.

Zurück zur Vortragsübersicht 

André Hernich