Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913863862059008 |
|---|---|
| author | Curticapean, Radu Döring, Simon Neuen, Daniel |
| author_facet | Curticapean, Radu Döring, Simon Neuen, Daniel |
| contents | We consider the parameterized problem $\#$IndSub$(Φ)$ for fixed graph properties $Φ$: Given a graph $G$ and an integer $k$, this problem asks to count the number of induced $k$-vertex subgraphs satisfying $Φ$. Dörfler et al. [Algorithmica 2022] and Roth et al. [SICOMP 2024] conjectured that $\#$IndSub$(Φ)$ is $\#$W[1]-hard for all non-meager properties $Φ$, i.e., properties that are nontrivial for infinitely many $k$. This conjecture has been confirmed for several restricted types of properties, including all hereditary properties [STOC 2022] and all edge-monotone properties [STOC 2024].
In this work, we refute this conjecture by showing that scorpion graphs, certain $k$-vertex graphs which were introduced more than 50 years ago in the context of the evasiveness conjecture, can be counted in time $O(n^4)$ for all $k$. A simple variant of this construction results in graph properties that achieve arbitrary intermediate complexity assuming ETH.
We formulate an updated conjecture on the complexity of $\#$IndSub$(Φ)$ that correctly captures the complexity status of scorpions and related constructions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_22300 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial Curticapean, Radu Döring, Simon Neuen, Daniel Computational Complexity Data Structures and Algorithms We consider the parameterized problem $\#$IndSub$(Φ)$ for fixed graph properties $Φ$: Given a graph $G$ and an integer $k$, this problem asks to count the number of induced $k$-vertex subgraphs satisfying $Φ$. Dörfler et al. [Algorithmica 2022] and Roth et al. [SICOMP 2024] conjectured that $\#$IndSub$(Φ)$ is $\#$W[1]-hard for all non-meager properties $Φ$, i.e., properties that are nontrivial for infinitely many $k$. This conjecture has been confirmed for several restricted types of properties, including all hereditary properties [STOC 2022] and all edge-monotone properties [STOC 2024]. In this work, we refute this conjecture by showing that scorpion graphs, certain $k$-vertex graphs which were introduced more than 50 years ago in the context of the evasiveness conjecture, can be counted in time $O(n^4)$ for all $k$. A simple variant of this construction results in graph properties that achieve arbitrary intermediate complexity assuming ETH. We formulate an updated conjecture on the complexity of $\#$IndSub$(Φ)$ that correctly captures the complexity status of scorpions and related constructions. |
| title | Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.22300 |