Sherali-Adams relaxations of graph isomorphism polytopes
Sherali-Adams relaxations of graph isomorphism polytopes
复制标题
图同构多面体的 Sherali-Adams 松弛
DOI：
10.1016/j.disopt.2014.01.004
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
P. Malkin
中科院分区：
文献类型：
--
作者：
P. Malkin
摘要本文研究了图同构多面体的Sherali-Adams提升与投影层次，该多面体的整数点表示两个图之间的同构。特别地，Sherali-Adams松弛刻画了一个新的图同构的顶点分类算法，我们称之为广义顶点分类算法。该算法推广了经典的顶点分类算法，推广了Tinhofer关于图自同构测试的多面体方法的工作。我们建立了Sherali-Adams提升与投影层次当应用于具有n个顶点的图的图同构多面体时，在最坏情况下需要Ω（n）次迭代才能收敛到整数点的凸船体。我们还表明，这种广义的顶点分类算法也是密切相关的著名的Weisfeiler-Lehman算法，我们也可以表现出的Sherali-Adams松弛的半代数集的整数点编码图同构。
Abstract We investigate the Sherali–Adams lift & project hierarchy applied to a graph isomorphism polytope whose integer points encode the isomorphisms between two graphs. In particular, the Sherali–Adams relaxations characterize a new vertex classification algorithm for graph isomorphism, which we call the generalized vertex classification algorithm. This algorithm generalizes the classic vertex classification algorithm and generalizes the work of Tinhofer on polyhedral methods for graph automorphism testing. We establish that the Sherali–Adams lift & project hierarchy when applied to a graph isomorphism polytope of a graph with n vertices needs Ω (n) iterations in the worst case before converging to the convex hull of integer points. We also show that this generalized vertex classification algorithm is also strongly related to the well-known Weisfeiler–Lehman algorithm, which we show can also be characterized in terms of the Sherali–Adams relaxations of a semi-algebraic set whose integer points encode graph isomorphisms.