论文标题
检测和枚举$ c $ claphs中的小型诱导子图
Detecting and Enumerating Small Induced Subgraphs in $c$-Closed Graphs
论文作者
论文摘要
Fox等。 [Siam J. Comp。 [2020]引入了一个新参数，称为$ c $ cluber，用于集体枚举问题的参数化研究。如果每对至少有$ c $ common Neighen的顶点邻近，则图形$ g $是$ c $的。 $ g $的$ c $ c $是最小的$ c $，因此$ g $是$ c $ cluc的。我们系统地探索了$ c $ c $门的影响对检测和枚举小型诱导子图的计算复杂性的影响。更确切地说，对于三到四个顶点上的每个图$ h $，我们研究了用于检测$ h $的参数化多项式时间算法，并在给定$ c $ clups的图中枚举所有出现$ h $的出现。
Fox et al. [SIAM J. Comp. 2020] introduced a new parameter, called $c$-closure, for a parameterized study of clique enumeration problems. A graph $G$ is $c$-closed if every pair of vertices with at least $c$ common neighbors is adjacent. The $c$-closure of $G$ is the smallest $c$ such that $G$ is $c$-closed. We systematically explore the impact of $c$-closure on the computational complexity of detecting and enumerating small induced subgraphs. More precisely, for each graph $H$ on three or four vertices, we investigate parameterized polynomial-time algorithms for detecting $H$ and for enumerating all occurrences of $H$ in a given $c$-closed graph.
