Isomorphism testing for embeddable graphs through definability
Martin Grohe · 2000
The k-dimensional Weisfeiler-Leman algorithm, for k 1, is a natural and simple combinatorial algorithm attempting to decide whether two given graphs are isomorphic. In this paper, we show that for every surface S (orientable or non-orientable) there is a k 1 such that the k-dimensional WL-algorithm succeeds to decide isomorphism of graphs embeddable in S. To prove this, we use a close connection between the WL-algorithm and denability in certain nite variable logics that has been established by Cai, Furer, and Immerman [7]. 1. INTRODUCTION The graph isomorphism problem asks whether two given graphs are isomorphic. While complexity theoretic results indicate that the isomorphism problem is not NP-complete (if it was, the polynomial hierarchy would collapse to its second level [6; 29]), no polynomial time algorithm for the general problem is known. However, there is a number of important classes of graphs on which the isomorphism problem is known to be solvable in polynomial t...