Counting Small Induced Subgraphs with Edge-monotone Properties

In this talk, we discuss the parameterized complexity of the #IndSub(Φ) problem. Given a graph G and a number k, the #IndSub(Φ) problem computes the number of induced subgraphs of size k of G that satisfy a fixed graph property Φ. In recent years, much research has focused on whether the problem #IndSub(Φ) is at least as hard as counting the number of k-cliques (#Clique) for a specific graph property Φ. We will extend this line of research by proving that #IndSub(Φ) is always at least as hard as #Clique whenever Φ is edge-monotone and nontrivial. Here, edge-monotone means that if a graph G satisfies a graph property Φ then all edge-subgraphs of G also satisfy Φ.