Paper Info
Title
The Graph Isomorphism Problem and approximate categories
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, Furer 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 v"1,v"2@?V, decide whether v"1 and v"2 lie in the same G-orbit. 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 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-Furer-Immerman graphs in polynomial time.
Year
DOI
Venue
2010
10.1016/j.jsc.2013.06.002
Journal of Symbolic Computation
Keywords
DocType
Volume
category c,approximate category,d-dimensional wl-algorithm,d-dimensional weisfeiler-lehman algorithm,isomorphism testing,orbit problem,elements v,polynomial time,cai-furer-immerman graph,graph isomorphism problem,weisfeiler-lehman algorithm,algebraic group,computational complexity,graph isomorphism
Journal
59,
ISSN
Citations 
PageRank 
0747-7171
2
0.42
References 
Authors
13
1
Name
Order
Citations
PageRank
Harm Derksen115115.00