Martin Grohe -Humboldt-Universität zu Berlin

The Complexity of Counting Short Paths and Cycles

Abstract: Deciding whether a graph H of size k is isomorphic to a subgraph of a graph G of size n by a naive brute-force algorithm requires time O(n^k). Parameterized complexity theory provides evidence that in general there is no substantially better algorithm. However, Alon, Yuster, and Zwick showed that if H is a path then the problem can be solved in expected time 2^{O(k)}·n or worst-case time 2^{O(k)}·n·log n. This means that for k \in O(log n) the problem can be solved in polynomial time. Only slightly worse bounds can be achieved for cycles H.

We study the corresponding counting problem. Our main result is that, modulo suitable reductions from parameterized complexity theory, the problem of counting short paths or cycles in a graph is as hard as the problem of counting arbitrary small subgraphs. (This is joint work with Jörg Flum.)

In this talk, I will introduce the necessary background from parameterized complexity theory, explain Alon, Yuster, and Zwick's randomized algorithm for the decision problem, and sketch a proof of the main hardness result.

Colloquium - 16 Uhr s.t.

cancelled -

Abstract: