Article ID Journal Published Year Pages File Type
401393 Journal of Symbolic Computation 2013 32 Pages PDF
Abstract

It is unknown whether two graphs can be tested for isomorphism in polynomial time. A classical approach to the Graph Isomorphism Problem is the d-dimensional Weisfeiler–Lehman algorithm. The d-dimensional WL-algorithm can distinguish many pairs of graphs, but the pairs of non-isomorphic graphs constructed by Cai, Fürer and Immerman it cannot distinguish. If d is fixed, then the WL-algorithm runs in polynomial time. We will formulate the Graph Isomorphism Problem as an Orbit Problem: Given a representation V of an algebraic group G   and two elements v1,v2∈Vv1,v2∈V, decide whether v1v1 and v2v2 lie in the same G  -orbit. Then we attack the Orbit Problem by constructing certain approximate categories CdCd, d∈N={1,2,3,…}d∈N={1,2,3,…} whose objects include the elements of V  . We show that v1v1 and v2v2 are not in the same orbit by showing that they are not isomorphic in the category CdCd for some d∈Nd∈N. For every d this gives us an algorithm for isomorphism testing. We will show that the WL-algorithms reduce to our algorithms, but that our algorithms cannot be reduced to the WL-algorithms. Unlike the Weisfeiler–Lehman algorithm, our algorithm can distinguish the Cai–Fürer–Immerman graphs in polynomial time.

Related Topics
Physical Sciences and Engineering Computer Science Artificial Intelligence
Authors
,