hide
Free keywords:
Computer Science, Computational Complexity, cs.CC
Abstract:
Given a graph property $\Phi$, the problem $\#\mathsf{IndSub}(\Phi)$ asks, on
input a graph $G$ and a positive integer $k$, to compute the number of induced
subgraphs of size $k$ in $G$ that satisfy $\Phi$. The search for explicit
criteria on $\Phi$ ensuring that $\#\mathsf{IndSub}(\Phi)$ 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\"orfler 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 $\Phi$, the problem $\#\mathsf{IndSub}(\Phi)$ cannot be solved in time
$f(k)\cdot |V(G)|^{o(k/ {\log^{1/2}(k)})}$ for any function $f$, 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 $\#\mathsf{W}[1]$-completeness
result.
