Counting Small Induced Subgraphs Satisfying Monotone Properties
Given a graph property <tex>\Phi$/tex> we study the problem <tex>\text{INDSUB}\Phi)/tex> which asks, on input a graph <tex>$G$/tex> and a positive integer <tex>$k$/tex> to compute the number <tex> \text{IndSub}\Phi, k\rightarrow G)/tex> of induced subgraphs of size <tex>$k$/tex> in <tex>$G$/tex> that satisfy <tex>\Phi$/tex> The search for explicit criteria on <tex>\Phi$/tex> ensuring that <tex> \text{INDSUB}\Phi)/tex> is hard was initiated by Jerrum and Meeks [J. Comput. Syst. Sci. 15] and is part of the major line of research on counting small patterns in graphs. However, apart from an implicit result due to Curticapean, Dell and Marx [STOC 17] proving that a full classification into "easy" and "hard" properties is possible and some partial results on edge monotone properties due to Meeks [Discret. Appl. Math. 16] and Dorfler et al. [MFCS 19] not much is known. In this work, we fully answer and explicitly classify the case of monotone, that is subgraph closed, properties: We show that for any non trivial monotone property <tex>\Phi$/tex> the problem <tex>\text{INDSUB}\Phi)/tex> cannot be solved in time <tex>$f(k) \vert V(G)\vert {o(k/\log^{1/2}(k)/tex> for any function <tex>$f$/tex> unless the Exponential Time Hypothesis fails. By this, we establish that any significant improvement over the brute force approach is unlikely; in the language of parameterized complexity, we also obtain a #W[1] completeness result.
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)