Graph Isomorphism, Color Refinement, and Compactness
Graph Isomorphism, Color Refinement, and Compactness
复制标题
图同构、颜色细化和紧致性
DOI：
10.1007/s00037-016-0147-6
复制
发表时间：
2017
影响因子：
1.4
通讯作者：
O. Verbitsky
中科院分区：
文献类型：
--
作者：
V. Arvind;J. Köbler;G. Rattan;O. Verbitsky
颜色细化是一种经典的技术，用于显示两个给定的图形不同构；它是非常有效的，尽管它不是在所有的图上都成功。如果颜色细化过程成功地将g与任何非同构的图h区分开来，则我们将其称为graphGamenableto颜色细化。Babai et al. （SIAM J computer 9(3): 628-635, 1980）已经证明随机图具有高概率可服从性。我们通过显示可修改的图在时间上是可识别的来确定颜色细化的确切适用范围，其中和表示输入图中的顶点数和边数。在紧图概念的基础上，利用可服从图的表征分析了图同构的实现方法。如果图的分数自同构的多面体是整的，则图称为紧的。Tinhofer（离散应用数学30(2-3):253-264,1991）指出紧图的同构检验可以通过线性规划相当有效地完成。然而，在多项式时间内表征紧图并识别它们的问题仍然是一个悬而未决的问题。我们在这个方向上的结果总结如下：换句话说，Tinhofer的线性规划方法对同态测试的适用范围至少与基于颜色细化的组合方法一样大。〇为了进一步探索颜色细化与紧性之间的关系，我们研究了Tinhofer和Godsil引入的相关组合图和代数图性质。我们证明了相应的图类形成了一个层次结构，并证明了识别这些图类是困难的。特别地，这给出了识别紧图的第一个复杂度下界。
Color refinementis a classical technique used to show that two given graphsGandHare non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a graphGamenableto color refinement if the color refinement procedure succeeds in distinguishingGfrom any non-isomorphic graphH. Babai et al. (SIAM J Comput 9(3):628–635, 1980) have shown that random graphs are amenable with high probability. We determine the exact range of applicability of color refinement by showing that amenable graphs are recognizable in time, wherenandmdenote the number of vertices and the number of edges in the input graph.We use our characterization of amenable graphs to analyze the approach to Graph Isomorphism based on the notion ofcompact graphs. A graph is called compact if the polytope of its fractional automorphisms is integral. Tinhofer (Discrete Appl Math 30(2–3):253–264, 1991) noted that isomorphism testing for compact graphs can be done quite efficiently by linear programming. However, the problem of characterizing compact graphs and recognizing them in polynomial time remains an open question. Our results in this direction are summarized below:○We show that all amenable graphs 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.
登录
查看更多内容
影响因子：
0.8
作者：
R. Tyshkevich
通讯作者：
R. Tyshkevich
关于与循环图相关的赋值多胞体的某些子多胞体的注释
影响因子：
1.1
作者：
H. Schreck;G. Tinhofer
通讯作者：
G. Tinhofer
单调和平面电路值问题对于 P 来说是对数空间完备的
DOI：
10.1145/1008354.1008356
发表时间：
1977
期刊：
SIGACT News
影响因子：
--
作者：
L. Goldschlager
通讯作者：
L. Goldschlager
关于紧致图
DOI：
10.1007/s10114-004-0485-1
发表时间：
2005
期刊：
Acta Mathematica Sinica
影响因子：
--
作者：
Ping Wang;Jiongsheng Li
通讯作者：
Jiongsheng Li
图算法与应用杂志 通过图的叠加进行单图识别
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
A. Borri;T. Calamoneri;R. Petreschi;S. Das;R. Uehara;A. Borri;T. Calamoneri;R. Petreschi
通讯作者：
R. Petreschi