Lovász Meets Weisfeiler and Leman
Lovász Meets Weisfeiler and Leman
复制标题
洛瓦斯会见魏斯费勒和莱曼
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Gaurav Rattan
中科院分区：
文献类型：
--
作者：
Holger Dell;Martin Grohe;Gaurav Rattan
在本文中，我们涉及一个美丽的理论，由Lov'asz与一个流行的启发式算法的图同构问题，即颜色细化算法和k维推广称为Weisfeiler-Leman算法。本文证明了两个图G和H是不可区分的当且仅当对于所有的树T，从T到G的同态数Hom（T，G）等于H的同态数Hom（T，H）。
存在一个自然的线性方程组，其非负整数解对应于两个图之间的同构。这个系统的非负真实的解称为分数同构，并且两个图是分数同构的当且仅当颜色细化算法不能区分它们（Tinhofer 1986，1991）。我们表明，如果我们下降的非负性约束，也就是说，如果我们寻找任意的真实的解决方案，然后一个解决方案的线性系统存在的当且仅当，对于所有的t，两个图有相同数量的长度-t行走。
我们提升树的结果，从树宽k，k维Weisfeiler-Leman算法，和我们的线性规划的水平k Sherali-Adams松弛图的同态数之间的等价。我们也得到了部分结果的图形有界路径宽度和解决方案，我们的系统，我们下降的非负性约束。我们的结果的一个后果是一个拟线性时间算法，以确定是否，对于两个给定的图G和H，有一棵树T与Hom（T，G）= Hom（T，H）。
In this paper, we relate a beautiful theory by Lov'asz with a popular heuristic algorithm for the graph isomorphism problem, namely the color refinement algorithm and its k-dimensional generalization known as the Weisfeiler-Leman algorithm. We prove that two graphs G and H are indistinguishable by the color refinement algorithm if and only if, for all trees T, the number Hom(T,G) of homomorphisms from T to G equals the corresponding number Hom(T,H) for H.
There is a natural system of linear equations whose nonnegative integer solutions correspond to the isomorphisms between two graphs. The nonnegative real solutions to this system are called fractional isomorphisms, and two graphs are fractionally isomorphic if and only if the color refinement algorithm cannot distinguish them (Tinhofer 1986, 1991). We show that, if we drop the nonnegativity constraints, that is, if we look for arbitrary real solutions, then a solution to the linear system exists if and only if, for all t, the two graphs have the same number of length-t walks.
We lift the results for trees to an equivalence between numbers of homomorphisms from graphs of tree width k, the k-dimensional Weisfeiler-Leman algorithm, and the level-k Sherali-Adams relaxation of our linear program. We also obtain a partial result for graphs of bounded path width and solutions to our system where we drop the nonnegativity constraints. A consequence of our results is a quasi-linear time algorithm to decide whether, for two given graphs G and H, there is a tree T with Hom(T,G) = Hom(T,H).
通用覆盖、颜色细化和二变量计数逻辑：深度的下界
DOI：
10.1109/lics.2015.69
发表时间：
2015
期刊：
2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
A. Krebs;O. Verbitsky
通讯作者：
O. Verbitsky