hide
Free keywords:
Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
We study the parameterized complexity of #IndSub($\Phi$), 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 graph property $\Phi$. Focke and Roth [STOC 2022]
completely characterized the complexity for each $\Phi$ that is a hereditary
property (that is, closed under vertex deletions): #IndSub($\Phi$) is
#W[1]-hard except in the degenerate cases when every graph satisfies $\Phi$ or
only finitely many graphs satisfy $\Phi$. We complement this result with a
classification for each $\Phi$ that is edge monotone (that is, closed under
edge deletions): #IndSub($\Phi$) is #W[1]-hard except in the degenerate case
when there are only finitely many integers $k$ such that $\Phi$ is nontrivial
on $k$-vertex graphs. Our result generalizes earlier results for specific
properties $\Phi$ that are related to the connectivity or density of the graph.
Further, we extend the #W[1]-hardness result by a lower bound which shows
that #IndSub($\Phi$) cannot be solved in time $f(k) \cdot |V(G)|^{o(\sqrt{\log
k/\log\log k})}$ for any function $f$, unless the Exponential-Time Hypothesis
(ETH) fails. For many natural properties, we obtain even a tight bound $f(k)
\cdot |V(G)|^{o(k)}$; for example, this is the case for every property $\Phi$
that is nontrivial on $k$-vertex graphs for each $k$ greater than some $k_0$.
