Counting and Detecting Small Subgraphs via Equations
Counting and Detecting Small Subgraphs via Equations
复制标题
通过方程计算和检测小子图
DOI：
--
复制
发表时间：
2013
影响因子：
0.8
通讯作者：
E. Lundell
中科院分区：
文献类型：
--
作者：
Miroslaw Kowaluk;A. Lingas;E. Lundell
我们提出了一种用于检测和计算小子图的通用技术。它包括形成图中固定大小的不同归纳子图的出现次数的特殊线性组合。这些组合可以通过矩形矩阵乘法有效地计算。我们利用该技术的两个主要结果如下。令 $H$ 为具有 $k$ 个顶点和一组独立的大小 $s 的固定图。$ 1. 检测 $n$ 顶点图是否包含与 $H$ 同构的（不一定是诱导的）子图可以及时完成 $O(n^{omega(lceil (k-s)/2)
天花板, 1, 地板 (k-s)/2
地板 )})$，其中 $omega (p,q,r)$ 是 $n^p imes n^q$ 矩阵与 $n^q imes n^r$ 矩阵的快速算术矩阵乘法的指数。 2. 当$s=2时，$计算与$H$同构的（不一定诱导的）子图的数量可以同时完成，即及时$O(n^{omega(lceil(k-2)/2)
天花板，1，地板 (k-2)/2
地板 )}).$ 特别是，我们可以计算 nu...
We present a general technique for detecting and counting small subgraphs. It consists of forming special linear combinations of the numbers of occurrences of different induced subgraphs of fixed size in a graph. These combinations can be efficiently computed by rectangular matrix multiplication. Our two main results utilizing the technique are as follows. Let $H$ be a fixed graph with $k$ vertices and an independent set of size $s.$ 1. Detecting if an $n$-vertex graph contains a (not necessarily induced) subgraph isomorphic to $H$ can be done in time $O(n^{omega(lceil (k-s)/2
ceil, 1, lfloor (k-s)/2
floor )})$, where $omega (p,q,r)$ is the exponent of fast arithmetic matrix multiplication of an $n^p imes n^q$ matrix by an $n^q imes n^r$ matrix. 2. When $s=2,$ counting the number of (not necessarily induced) subgraphs isomorphic to $H$ can be done in the same time, i.e., in time $O(n^{omega(lceil (k-2)/2
ceil, 1, lfloor (k-2)/2
floor )}).$ It follows in particular that we can count the nu...