On the complexity of subgraph counting, parameterized by degeneracy and outdegree

Counting induced subgraphs, counting subgraphs, and counting homomorphisms are three fundamental graph problems. While their fixed-parameter tractability is well understood when the parameter is just the size of the pattern, in this talk I will consider what happens when one adds as a parameter the degeneracy of the host graph or, in the directed versions of the problems, its maximum outdegree. I will show that, somewhat surprisingly, under both parameterizations we can completely characterize the fixed-parameter tractability of all problems except for the homomorphism counting one, which remains open despite the crucial role it plays in all our results.

The talk is based on joint work with Matthias Lanzinger and Marc Roth.