Improved random graph isomorphism

Canonical labeling of a graph consists of assigning a unique label to each vertex such that the labels are invariant under isomorphism. Such a labeling can be used to solve the graph isomorphism problem. We give a simple, linear time, high probability algorithm for the canonical labeling of a G(n,p)G(n,p) random graph for p∈[ω(ln4n/nlnlnn),1−ω(ln4n/nlnlnn)]p∈[ω(ln4n/nlnlnn),1−ω(ln4n/nlnlnn)]. Our result covers a gap in the range of p   in which no algorithm was known to work with high probability. Together with a previous result by Bollobás, the random graph isomorphism problem can be solved efficiently for p∈[Θ(lnn/n),1−Θ(lnn/n)]p∈[Θ(lnn/n),1−Θ(lnn/n)].