We consider the fundamental problem of detecting/counting copies of a fixed pattern graph in a host graph. The recent progress on this problem has not included complete pattern graphs, i.e., cliques (and their complements, i.e., edge-free pattern graphs, in the induced setting). The fastest algorithms for the aforementioned patterns are based on a straightforward reduction to triangle detection/counting. We provide an alternative method of detection/counting copies of fixed size cliques based on a multi-dimensional matrix product. It is at least as time efficient as the triangle method in cases of $K_4$ and $K_5.$ The complexity of the multi-dimensional matrix product is of interest in its own rights. We provide also another alternative method for detection/counting $K_r$ copies, again time efficient for $r\in \{ 4,\ 5 \}$.
翻译:我们考虑了在主机图中探测/计算固定图案副本的根本问题,这个问题最近的进展没有包括完整的图案图案,即在诱导环境下的 cliques(及其补充,即无边图案图案),上述图案最快的算法是以直截了当地减少三角探测/计算为基础的。我们提供了一种基于多维矩阵产品的固定大小的样板的探测/计算替代方法。在4美元和5美元的情况下,它至少与三角法一样有效。多维矩阵产品的复杂性关系到其本身的权利。我们还提供了另一种探测/计算$_r$副本的替代方法,对于$_4,\ 5美元来说再次有效。