Comment by procedurecall

You may be interested in Mahaney's Theorem (https://en.m.wikipedia.org/wiki/Mahaney%27s_theorem), which 'answers' a special case of this: If by vanishingly small you mean polynomial size, and you also assume Alice has an algorithm that can distinguish the two subclasses of graph isomorphism, then P=NP if Alice has these facts. By 'distinguish', I specifically mean that Alice has a polynomial time algorithm that will tell you, for an input of graph isomorphism, is it part of a subclass of graph isomorphism which is NP-complete, and which has polynomial size.