# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Counting Small Induced Subgraphs with Edge-monotone Properties

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

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

##### Fulltext (public)

arXiv:2311.08988.pdf

(Preprint), 2MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Döring, S., Marx, D., & Wellnitz, P. (2023). Counting Small Induced Subgraphs with Edge-monotone Properties. Retrieved from https://arxiv.org/abs/2311.08988.

Cite as: https://hdl.handle.net/21.11116/0000-000F-1442-0

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

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