论文标题
工程快速概率同构测试
Engineering a Fast Probabilistic Isomorphism Test
论文作者
论文摘要
我们为同构测试设计了一种新的概率蒙特卡洛算法。最值得注意的是，与所有其他求解器相反，它隐含地利用了对称性的存在，而无需明确计算它们。 我们提供了广泛的基准测试，表明该算法在大多数输入中的同构测试的所有最新解决方案都超过了同构标准基准库中的同构基准库来进行同构测试。在许多输入类型上，我们的数据不仅显示了一个数量级的改善运行时间，而且还反映了更好的渐近行为。 我们的结果表明，使用当前的算法，同构测试比计算自动形态组或典型标记图的相关问题要容易得多。结果还表明，对于同构测试的概率算法也可以设计成超出确定性方法，即使是渐近的方法。
We engineer a new probabilistic Monte-Carlo algorithm for isomorphism testing. Most notably, as opposed to all other solvers, it implicitly exploits the presence of symmetries without explicitly computing them. We provide extensive benchmarks, showing that the algorithm outperforms all state-of-the-art solutions for isomorphism testing on most inputs from the de facto standard benchmark library for isomorphism testing. On many input types, our data not only show improved running times by an order of magnitude, but also reflect a better asymptotic behavior. Our results demonstrate that, with current algorithms, isomorphism testing is in practice easier than the related problems of computing the automorphism group or canonically labeling a graph. The results also show that probabilistic algorithms for isomorphism testing can be engineered to outperform deterministic approaches, even asymptotically.
