# graph isomorphism given a partial isomorphism

Is there an approach to graph isomorphism considering that we are already given a partial isomorphism ? In particular, it would be interesting to have conditions on this partial isomorphism that makes the problem polynomial.

This question arises from automata theory, where one approach to testing equivalence of two NFAs on alphabet $A$ is to compute their syntactic semigroups $M_1,M_2$ (of exponential size) together with functions $h_1:A\to M_1$, $h_2: A\to M_2$. Testing semigroup isomorphism is hard in the general case, but here we can do it polynomially, because $h_1,h_2$ already give us a partial isomorphism for a set of generators, which is enough.

For graphs, an obvious sufficent condition for such a partial isomorphism to make the problem polynomial would be "containing a covering set" (in the sense each edge contains a vertex in it) . Maybe there are more subtle conditions that would still work ?

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 > 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-.

• Nice reference. Why is "Conference on Computational Complexity" abbreviated as COCO instead of CCC? Apr 5 '14 at 19:44
• @HuckBennett: I copied/pasted the acm.org "ACM Ref" format (on the right of the dl.acm.org pages). Apr 5 '14 at 19:51
• Yes, I was asking why it was abbreviated that way on the ACM page. Apr 5 '14 at 19:57
• @HuckBennett: I think it was its original abbreviation ?!? Apr 5 '14 at 20:01
• @HuckBennett: I don't know the actual history, but according to DBLP the abbreviation changed from CoCo to CCC in 2003: informatik.uni-trier.de/~ley/db/conf/coco Apr 6 '14 at 3:59

It's not clear whether you seek a complexity result or you really wish to solve the problem in practice (therefore admitting heuristics), but maybe you should look into e.g. the works of Karem Sakallah on graph automorphisms.

• I'm seeking a complexity result. Maybe this approach could lead to heuristic algorithms for the part that gets the partial isomorphism in the first place, but it's not in the scope of the question. Apr 6 '14 at 12:08