We prove that the conjugacy problem for the automorphism group of the random graph is Borel complete, and discuss the analogous problem for some other countably categorical structures.

We show that for any countable homogeneous ordered graph G, the conjugacy problem for automorphisms of G is Borel complete. In fact we establish that each such G satisfies a strong extension property called ABAP, which implies that the isomorphism relation on substructures of G is Borel reducible to the conjugacy relation on automorphisms of G.