Lecture by Holger Dell (IT University of Copenhagen): Counting and sampling small subgraphs

Jan 20, 2020 | 02:15 PM

In this talk, we discuss various algorithmic techniques used for counting and sampling subgraphs in a large input graph. The focus of the talk is on the mathematical foundations. We start with the beautiful technique of Color-Coding (Alon, Yuster, Zwick 1995), and we discuss various generalizations based on group algebras (Koutis 2008) and on the exterior algebra (Brand, D, Husfeldt 2018). These techniques are most useful for sampling, which is equivalent to approximate counting. On the other hand, the fastest known algorithm to exactly count subgraphs that are isomorphic to a graph H  (Curticapean, D, Marx 2017) is based on the foundations of Lovász' theory of graph limits.

Time & Location

Jan 20, 2020 | 02:15 PM

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
Room 005 (Ground Floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)