We consider the problems #Sub(C) for fixed graph classes C: Given as input a graph H from C (the pattern) and another graph G, count the occurrences of H as a subgraph in G. Our goal is to understand which properties of the pattern class C make the problem #Sub(C) easy/hard. For instance, for the class of stars, we can solve this problem in linear time. For the class of paths however, it subsumes counting Hamiltonian paths and is hence #P-hard.

 

As it turns out, the mere assumption of FP not being equal to #P fails to give a sweeping dichotomy for this problem, since there exist intermediate problems. However, adopting the framework of fixed-parameter tractability, we show how to classify the problems #Sub(C) as either polynomial-time solvable or #W[1]-hard: A class C lies on the "easy" side of this dichotomy if the graphs appearing in it have vertex-covers of constant size.

 

We will obtain similar dichotomies for the problems of counting colored subgraphs, for counting subgraphs modulo fixed numbers, and for other variations of the problem. These results show that parameterized complexity theory, apart from being interesting on its own, can help to obtain "classical" dichotomies.

 

The talk will be self-contained and begins with an introduction to the necessary concepts from parameterized complexity.