On Tinhofer's Linear Programming Approach to Isomorphism Testing
On Tinhofer's Linear Programming Approach to Isomorphism Testing
复制标题
关于 Tinhofer 的同构测试线性规划方法
DOI：
10.1007/978-3-662-48054-0_3
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
O. Verbitsky
中科院分区：
文献类型：
--
作者：
V. Arvind;J. Köbler;G. Rattan;O. Verbitsky
Tinhofer（1991）在探索图同构的线性规划方法时，定义了紧图的概念：一个图是紧的，如果它的分数自同构的多面体是整数。丁霍夫指出，紧凑图的同构测试可以通过线性规划非常有效地完成。然而，在多项式时间内刻画和识别紧图的问题仍然是一个悬而未决的问题。本文在紧图的认识上取得了新的进展。我们的结果总结如下：我们证明了所有的图G，这是区别于任何非同构的经典的颜色细化程序是紧凑的。换句话说，Tinhofer的线性规划方法的同构测试的适用范围至少是一样大的组合方法的基础上的颜色refinement.Exploring颜色细化和紧凑性之间的关系进一步，我们研究相关的组合和代数图形的性质介绍Tinhofer和Godsil。我们表明，相应的类的图形成一个层次结构，我们证明，这些图类的识别是P-硬。特别地，这给出了识别紧致图的第一复杂性下界。
Exploring a linear programming approach to Graph Isomorphism, Tinhofer (1991) defined the notion ofcompact graphs: A graph iscompactif the polytope of its fractional automorphisms is integral. Tinhofer noted that isomorphism testing for compact graphs can be done quite efficiently by linear programming. However, the problem of characterizing and recognizing compact graphs in polynomial time remains an open question. In this paper we make new progress in our understanding of compact graphs. Our results are summarized below:We show that all graphsGwhich are distinguishable from any non-isomorphic graph by the classical color-refinement procedure are compact. In other words, the applicability range for Tinhofer’s linear programming approach to isomorphism testing is at least as large as for the combinatorial approach based on color refinement.Exploring the relationship between color refinement and compactness further, we study related combinatorial and algebraic graph properties introduced by Tinhofer and Godsil. We show that the corresponding classes of graphs form a hierarchy and we prove that recognizing each of these graph classes isP-hard. In particular, this gives a first complexity lower bound for recognizing compact graphs.
登录
查看更多内容
关于与循环图相关的赋值多胞体的某些子多胞体的注释
影响因子：
1.1
作者：
H. Schreck;G. Tinhofer
通讯作者：
G. Tinhofer
关于紧致图
DOI：
10.1007/s10114-004-0485-1
发表时间：
2005
期刊：
Acta Mathematica Sinica
影响因子：
--
作者：
Ping Wang;Jiongsheng Li
通讯作者：
Jiongsheng Li
DOI：
--
发表时间：
1990
期刊：
影响因子：
--
作者：
N. Immerman;E. Lander
通讯作者：
E. Lander
图同构、颜色细化和紧致性
影响因子：
1.4
作者：
V. Arvind;J. Köbler;G. Rattan;O. Verbitsky
通讯作者：
O. Verbitsky
有限变量逻辑中的等价性对于多项式时间是完全的
影响因子：
1.1
作者：
Martin Grohe
通讯作者：
Martin Grohe