Details:
Title  The Graph Isomorphism Problem and approximate categories  Author(s)  Harm Derksen  Type  Article in Journal  Abstract  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 ddimensional Weisfeiler–Lehman algorithm. The ddimensional WLalgorithm can distinguish many pairs of graphs, but the pairs of nonisomorphic graphs constructed by Cai, Fürer and Immerman it cannot distinguish. If d is fixed, then the WLalgorithm 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 v_1 , v_2 ∈ V , decide whether v 1 and v 2 lie in the same Gorbit. Then we attack the Orbit Problem by constructing certain approximate categories C_d , d ∈ N = 1 , 2 , 3 , … whose objects include the elements of V. We show that v 1 and v 2 are not in the same orbit by showing that they are not isomorphic in the category C_d for some d ∈ N . For every d this gives us an algorithm for isomorphism testing. We will show that the WLalgorithms reduce to our algorithms, but that our algorithms cannot be reduced to the WLalgorithms. Unlike the Weisfeiler–Lehman algorithm, our algorithm can distinguish the Cai–Fürer–Immerman graphs in polynomial time.  Keywords  Graph Isomorphism Problem, Weisfeiler–Lehman algorithm, Complexity Theory, Categories  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S074771711300093X 
Language  English  Journal  Journal of Symbolic Computation  Volume  59  Number  0  Pages  81  112  Year  2013  Edition  0  Translation 
No  Refereed 
No 
