Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleThe Graph Isomorphism Problem and approximate categories
Author(s) Harm Derksen
TypeArticle in Journal
AbstractAbstract 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 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–Fürer–Immerman graphs in polynomial time.
KeywordsGraph Isomorphism Problem, Weisfeiler–Lehman algorithm, Complexity Theory, Categories
URL http://www.sciencedirect.com/science/article/pii/S074771711300093X
JournalJournal of Symbolic Computation
Pages81 - 112
Translation No
Refereed No