hide
Free keywords:
Computer Science, Computational Complexity
Abstract:
We investigate the problem $\#\mathsf{IndSub}(\Phi)$ of counting all induced
subgraphs of size $k$ in a graph $G$ that satisfy a given property $\Phi$. This
continues the work of Jerrum and Meeks who proved the problem to be
$\#\mathrm{W[1]}$-hard for some families of properties which include, among
others, (dis)connectedness [JCSS 15] and even- or oddness of the number of
edges [Combinatorica 17]. Using the recent framework of graph motif parameters
due to Curticapean, Dell and Marx [STOC 17], we discover that for monotone
properties $\Phi$, the problem $\#\mathsf{IndSub}(\Phi)$ is hard for
$\#\mathrm{W[1]}$ if the reduced Euler characteristic of the associated
simplicial (graph) complex of $\Phi$ is non-zero. This observation links
$\#\mathsf{IndSub}(\Phi)$ to Karp's famous Evasiveness Conjecture, as every
graph complex with non-vanishing reduced Euler characteristic is known to be
evasive. Applying tools from the "topological approach to evasiveness" which
was introduced in the seminal paper of Khan, Saks and Sturtevant [FOCS 83], we
prove that $\#\mathsf{IndSub}(\Phi)$ is $\#\mathrm{W[1]}$-hard for every
monotone property $\Phi$ that does not hold on the Hamilton cycle as well as
for some monotone properties that hold on the Hamilton cycle such as being
triangle-free or not $k$-edge-connected for $k > 2$. Moreover, we show that for
those properties $\#\mathsf{IndSub}(\Phi)$ can not be solved in time $f(k)\cdot
n^{o(k)}$ for any computable function $f$ unless the Exponential Time
Hypothesis (ETH) fails. In the final part of the paper, we investigate
non-monotone properties and prove that $\#\mathsf{IndSub}(\Phi)$ is
$\#\mathrm{W[1]}$-hard if $\Phi$ is any non-trivial modularity constraint on
the number of edges with respect to some prime $q$ or if $\Phi$ enforces the
presence of a fixed isolated subgraph.
