标题： 计算小诱导子图：蝎子是简单的但不平凡 显示英文标题

标题： Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial

摘要： 我们考虑参数化问题$\#$IndSub$(\Phi)$对于固定的图性质$\Phi$：给定一个图$G$和一个整数$k$，该问题要求计算满足$\Phi$的诱导$k$-顶点子图的数量。 多弗勒等人 [Algorithmica 2022] 和罗斯等人 [SICOMP 2024] 猜想，对于所有非平凡性质 $\Phi$（即对于无穷多个 $k$非平凡的性质），$\#$IndSub$(\Phi)$是$\#$W[1]-困难的。 这一猜想已经针对几种受限类型的性质得到了证实，包括所有遗传性质 [STOC 2022] 和所有边单调性质 [STOC 2024]。 在这项工作中，我们通过证明蝎子图是可以计数的（蝎子图是某种 $k$-顶点图，在关于可规避性猜想的研究中首次引入已有50多年），反驳了这一猜想，这些图可以在时间 $O(n^4)$内被计算，适用于所有 $k$。 这个构造的一个简单变体，在假设指数时间假设 (ETH) 下，会导致具有任意中间复杂度的图性质。 我们提出了一个更新的关于 $\#$IndSub$(\Phi)$ 复杂性的猜想，该猜想正确地反映了蝎子图及相关构造的复杂性状态。 显示英文摘要

摘要： We consider the parameterized problem $\#$IndSub$(\Phi)$ for fixed graph properties $\Phi$: Given a graph $G$ and an integer $k$, this problem asks to count the number of induced $k$-vertex subgraphs satisfying $\Phi$. D\"orfler et al. [Algorithmica 2022] and Roth et al. [SICOMP 2024] conjectured that $\#$IndSub$(\Phi)$ is $\#$W[1]-hard for all non-meager properties $\Phi$, 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$(\Phi)$ that correctly captures the complexity status of scorpions and related constructions.