Computing the partition function for graph homomorphisms with multiplicities
Computing the partition function for graph homomorphisms with multiplicities
复制标题
计算具有多重性的图同态的配分函数
DOI：
10.1016/j.jcta.2015.08.001
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
P. Soberón
中科院分区：
文献类型：
--
作者：
A. Barvinok;P. Soberón
我们考虑图同态配分函数的细化，并提出一种拟多项式算法来在特定域中计算它。作为推论，我们获得了用于计算独立集、完美匹配、哈密顿循环和图中密集子图以及图着色的配分函数的拟多项式算法。这使我们能够在拟多项式时间图中区分出距离具有给定类型的结构（即给定大小的独立集、哈密顿循环等）足够远的图与具有足够多的该类型结构的图，即使随机命中这种结构的概率呈指数级小。
We consider a refinement of the partition function of graph homomorphisms and present a quasi-polynomial algorithm to compute it in a certain domain. As a corollary, we obtain quasi-polynomial algorithms for computing partition functions for independent sets, perfect matchings, Hamiltonian cycles and dense subgraphs in graphs as well as for graph colorings. This allows us to tell apart in quasi-polynomial time graphs that are sufficiently far from having a structure of a given type (i.e., independent set of a given size, Hamiltonian cycle, etc.) from graphs that have sufficiently many structures of that type, even when the probability to hit such a structure at random is exponentially small.