graph isomorphism given a partial isomorphism
Only an extended comment: Lipton et al. proved [1] that if we have access to an oracle that given two graphs on $n$ vertices, reveals a partial map on at least $(3+\epsilon)\log n$ vertices (for some constant $\epsilon &gt; 0$) which is part of an isomorpshism between the two graphs, then we can find the isomorphism in polynomial time.

The theorem deals with finding the isomorphism (the two graphs must  be  isomorphic), and the oracle is obviously called multiple times.

[1] Anna Gál, Shai Halevi, Erez Petrank, and Richard Lipton. 1999. Computing From Partial Solutions. In Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity (COCO '99). IEEE Computer Society, Washington, DC, USA, 34-.