论文标题
计算满足单调特性的小诱导子图
Counting Small Induced Subgraphs Satisfying Monotone Properties
论文作者
论文摘要
给定图形属性$φ$，问题$ \ \＃\ Mathsf {indsub}（φ）$问，输入图$ g $和一个正整数$ k $，以计算满足$φ$的$ g $中的$ g $中的$ k $的诱导子级数量。在$φ$上搜索明确的标准，以确保$ \＃\ Mathsf {indsub}（φ）$由Jerrum和Meeks启动很难[J. J. [J.计算。系统。科学。 15]，是计算图中小模式的主要研究的一部分。但是，除了由于Curticapean，Dell和Marx [Stoc 17]引起的隐式结果外，还出现了“简单”和“硬”属性的完整分类，并且由于温和[Diptect [distect]而导致边缘 - 单酮特性的某些部分结果。应用。数学。 16]和Dörfler等。 [MFCS 19]，尚不清楚。 在这项工作中，我们充分回答并明确对单调的情况进行了分类，该案例已封闭，属性：我们表明，对于任何非客气单调属性$φ$，问题$ \ \＃\ althsf {Indsub}（φ）$无法在时间$ f（k）\ cdot \ cdot | v（k）| {\ log^{1/2}（k）}）} $对于任何函数$ f $，除非指数时间假设失败。通过这种情况，我们确定对蛮力方法的任何重大改进都是不可能的。在参数化复杂性的语言中，我们还获得了$ \＃\ Mathsf {w} [1] $ - 完整性结果。
Given a graph property $Φ$, the problem $\#\mathsf{IndSub}(Φ)$ asks, on input a graph $G$ and a positive integer $k$, to compute the number of induced subgraphs of size $k$ in $G$ that satisfy $Φ$. The search for explicit criteria on $Φ$ ensuring that $\#\mathsf{IndSub}(Φ)$ is hard was initiated by Jerrum and Meeks [J. Comput. Syst. Sci. 15] and is part of the major line of research on counting small patterns in graphs. However, apart from an implicit result due to Curticapean, Dell and Marx [STOC 17] proving that a full classification into "easy" and "hard" properties is possible and some partial results on edge-monotone properties due to Meeks [Discret. Appl. Math. 16] and Dörfler et al. [MFCS 19], not much is known. In this work, we fully answer and explicitly classify the case of monotone, that is subgraph-closed, properties: We show that for any non-trivial monotone property $Φ$, the problem $\#\mathsf{IndSub}(Φ)$ cannot be solved in time $f(k)\cdot |V(G)|^{o(k/ {\log^{1/2}(k)})}$ for any function $f$, unless the Exponential Time Hypothesis fails. By this, we establish that any significant improvement over the brute-force approach is unlikely; in the language of parameterized complexity, we also obtain a $\#\mathsf{W}[1]$-completeness result.
