Benchmark Graphs for Practical Graph Isomorphism
Benchmark Graphs for Practical Graph Isomorphism
复制标题
实用图同构的基准图
DOI：
10.4230/lipics.esa.2017.60
复制
发表时间：
2017
影响因子：
4.3
通讯作者：
Pascal Schweitzer
中科院分区：
文献类型：
--
作者：
Daniel Neuen;Pascal Schweitzer
图同构问题的最先进的求解器可以很容易地解决具有数万个顶点的通用实例。事实上，实验表明，在没有特定组合结构的输入上，算法几乎线性扩展。事实上，为这样的求解器创建具有挑战性的实例是不平凡的，并且可用的困难基准图的数量非常有限。我们描述了一种构造，以有效地生成小的实例，图同构问题是困难的，甚至是不可行的，所述求解器。到目前为止，对同构求解器构成挑战的唯一其他可用实例是组合对象的某些关联结构（如投影平面，Hadamard矩阵，拉丁方等）。实验表明，从1500个顶点开始，我们的新实例在可比的输入大小上要困难几个数量级。更重要的是，我们的方法是通用的和有效的意义上说，一个可以快速创建所需数量的顶点上的同构实例。与此相反，所述组合对象是罕见的并且难以生成，并且利用新构造，可以生成任意大小的大量实例。我们的建设取决于多足的Gurevich和Shelah和Cai-F\"{u}rer-Immerman小工具，实现了一定的阿贝尔自同构群，并多次发挥了作用的上下文中的图同构。探索这种结构的限制，我们还解释说，有群论的障碍，推广建设与非阿贝尔小工具。
The state-of-the-art solvers for the graph isomorphism problem can readily solve generic instances with tens of thousands of vertices. Indeed, experiments show that on inputs without particular combinatorial structure the algorithms scale almost linearly. In fact, it is non-trivial to create challenging instances for such solvers and the number of difficult benchmark graphs available is quite limited. We describe a construction to efficiently generate small instances for the graph isomorphism problem that are difficult or even infeasible for said solvers. Up to this point the only other available instances posing challenges for isomorphism solvers were certain incidence structures of combinatorial objects (such as projective planes, Hadamard matrices, Latin squares, etc.). Experiments show that starting from 1500 vertices our new instances are several orders of magnitude more difficult on comparable input sizes. More importantly, our method is generic and efficient in the sense that one can quickly create many isomorphism instances on a desired number of vertices. In contrast to this, said combinatorial objects are rare and difficult to generate and with the new construction it is possible to generate an abundance of instances of arbitrary size. Our construction hinges on the multipedes of Gurevich and Shelah and the Cai-F\"{u}rer-Immerman gadgets that realize a certain abelian automorphism group and have repeatedly played a role in the context of graph isomorphism. Exploring limits of such constructions, we also explain that there are group theoretic obstructions to generalizing the construction with non-abelian gadgets.