We introduce graph motif parameters, a class of graph parameters that depend only on the
frequencies of constant-size induced subgraphs. Classical works by Lovász show that many …

For a class C of graphs,# Sub (C) is the counting problem that, given a graph H from C and
an arbitrary graph G, asks for the number of subgraphs of G isomorphic to H. It is known that …

For a fixed graph property Φ and integer k≥ 1, consider the problem of counting the induced
k-vertex subgraphs satisfying Φ in an input graph G. This problem can be solved by brute …

In this thesis, we study the parameterized complexity of counting problems, as introduced by
Flum and Grohe. This area mainly involves questions of the following kind: On inputs x with …

We study the computational complexity of the problem# IndSub (Φ) of counting k-vertex
induced subgraphs of a graph G that satisfy a graph property Φ. Our main result establishes …

We study the parameterized complexity of# IndSub (Φ), where given a graph G and an
integer k, the task is to count the number of induced subgraphs on k vertices that satisfy the …

We introduce a family of parameterised counting problems on graphs, p-# Induced
Subgraph With Property (Φ), which generalises a number of problems which have …

Parameterised subgraph counting problems are the most thoroughly studied topic in the
theory of parameterised counting, and there has been significant recent progress in this …

A graph property is a function Φ that maps every graph to {0, 1} and is invariant under
isomorphism. In the# IndSub (Φ) problem, given a graph G and an integer k, the task is to …

This survey is an invitation to parameterized counting problems for readers with a
background in parameterized algorithms and complexity. After an introduction to the …