Computing the Number of Induced Copies of a Fixed Graph in a Bounded Degree Graph
Computing the Number of Induced Copies of a Fixed Graph in a Bounded Degree Graph
复制标题
DOI：
10.1007/s00453-018-0511-9
复制
发表时间：
2019-05-01
期刊：
影响因子：
1.1
通讯作者：
Regts, Guus
中科院分区：
文献类型：
--
作者：
Patel, Viresh;Regts, Guus
本文证明了对于任意m阶图H和任意n阶最大度Delta图G，当c = c（Delta）> 0时，可以计算出V（G）的子集S在时间O（c（m）·n）上导出同构于H的图的个数.这基本上是最好的可能（在指数时间假设下没有c（o（m））poly（n）-time算法）。
In this paper we show that for any graph H of order m and any graph G of order n and maximum degree Delta one can compute the number of subsets S of V(G) that induces a graph isomorphic to H in time O(c(m).n) for some constant c = c(Delta) > 0. This is essentially best possible (in the sense that there is no c(o(m)) poly(n)-time algorithm under the exponential time hypothesis).