  We define a search problem on trees that closely captures the backtracking
behavior of all current practical graph isomorphism algorithms. Given two trees
with colored leaves, the goal is to find two leaves of matching color, one in
each of the trees. The trees are subject to an invariance property which
promises that for every pair of leaves of equal color there must be a symmetry
(or an isomorphism) that maps one leaf to the other.
  We describe a randomized algorithm with errors for which the number of
visited leaves is quasilinear in the square root of the size of the smaller of
the two trees. For inputs of bounded degree, we develop a Las Vegas algorithm
with a similar running time.
  We prove that these results are optimal up to logarithmic factors. We show a
lower bound for randomized algorithms on inputs of bounded degree that is the
square root of the tree sizes. For inputs of unbounded degree, we show a linear
lower bound for Las Vegas algorithms. For deterministic algorithms we can prove
a linear bound even for inputs of bounded degree. This shows why randomized
algorithms outperform deterministic ones.
  Our results explain why the randomized "breadth-first with intermixed
experimental path" search strategy of the isomorphism tool Traces (Piperno
2008) is often superior to the depth-first search strategy of other tools such
as nauty (McKay 1977) or bliss (Junttila, Kaski 2007). However, our algorithm
also provides a new traversal strategy, which is theoretically near optimal
with better worst case behavior than traversal strategies that have previously
been used.
