The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance
Eldar Fischer · SIAM Journal on Computing · 2005
Motivated by a question from [E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky, J. Comput. System Sci., 68 (2004), pp. 753--787], we investigate the number of queries required for testing that an input graph G is isomorphic to a fixed graph H that is given in advance. We correlate this number with a measure of the "complexity" of H that we define here, by proving both an upper bound and a lower bound on the number of queries that depends on this new measure. As far as we know this is the first characterization of this type for graphs.