| Summary: | <p>Given a graph property <span tabindex="0">Φ</span> , we study the problem <span tabindex="0">#INDSUB(Φ)</span> which asks, on input a graph <span tabindex="0">G</span> and a positive integer <span tabindex="0">k</span> , to compute the number <span tabindex="0">#IndSub(Φ,k→G)</span> of induced subgraphs of size <span tabindex="0">k</span> in <span tabindex="0">G</span> that satisfy <span tabindex="0">Φ</span> . The search for explicit criteria on <span tabindex="0">Φ</span> ensuring that <span tabindex="0">#INDSUB(Φ)</span> 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 Dörfler 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 <span tabindex="0">Φ</span> , the problem <span tabindex="0">#INDSUB(Φ)</span> cannot be solved in time <span tabindex="0">f(k).|V(G)|o(k/log1/2(k))</span> for any function <span tabindex="0">f</span> , 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.</p>
|
|---|