



























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。