# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Counting induced subgraphs: a topological approach to #W[1]-hardness

##### External Resource

https://doi.org/10.1007/s00453-020-00676-9

(Publisher version)

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

Roth-Schmitt_Counting Induced Subgraphs_2020.pdf

(Publisher version), 3MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Roth, M., & Schmitt, J. (2020). Counting induced subgraphs: a topological approach
to #W[1]-hardness.* Algorithmica,* *82*(8), 2267-2291. doi:10.1007/s00453-020-00676-9.

Cite as: https://hdl.handle.net/21.11116/0000-0008-BAD7-4

##### 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.

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.