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

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

<p>[1] Anna Gál, Shai Halevi, Erez Petrank, and Richard Lipton. 1999. <a href="http://dl.acm.org/citation.cfm?id=793388">Computing From Partial Solutions.</a> In Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity (COCO '99). IEEE Computer Society, Washington, DC, USA, 34-. </p>

CC BY-SA 3.0
2014-04-05T19:44:36.817Z
Nice reference. Why is "Conference on Computational Complexity" abbreviated as COCO instead of CCC?
Huck Bennett
CC BY-SA 3.0
2014-04-05T19:51:17.093Z
@HuckBennett: I copied/pasted the acm.org "ACM Ref" format (on the right of the dl.acm.org pages).
Marzio De Biasi
CC BY-SA 3.0
2014-04-05T19:57:54.080Z
Yes, I was asking why it was abbreviated that way on the ACM page.
Huck Bennett
CC BY-SA 3.0
2014-04-05T20:01:21.343Z
@HuckBennett: I think it was its original abbreviation ?!?
Marzio De Biasi
CC BY-SA 3.0
2014-04-06T03:59:07.653Z
@HuckBennett: I don't know the actual history, but according to DBLP the abbreviation changed from CoCo to CCC in 2003: http://www.informatik.uni-trier.de/~ley/db/conf/coco/
Joshua Grochow
CC BY-SA 3.0
2014-04-06T12:05:45.473Z
Thanks, nice reference, although the approach is a little different.
Denis
CC BY-SA 3.0
2014-04-06T23:32:15.067Z
@JoshuaGrochow: Thanks, I didn't realize that both the name and abbreviation had changed over time.
Huck Bennett
CC BY-SA 3.0
2016-03-23T10:18:05.580Z
@JoshuaGrochow , Assume, graphs $G, H$ are not isomorphic, but there exists a partial isomorphism of $(3+\epsilon)\log n$ vertices, is there a chance, that the  algorithm based on Lipton's paper would  provide an isomorphsim?
Michael
CC BY-SA 3.0
2016-03-23T14:59:30.387Z
@Jim: As far as I understand it, Lipton et al. would only yield an isomorphism if there *was* an isomorphism that extended the partial isomorphism. (Merely having an isomorphism between two subgraphs of size $(3+\epsilon)\log n)$ seems to not be enough...)
Joshua Grochow
CC BY-SA 3.0
2016-03-24T05:23:34.880Z
@Jim: Of course there is no such bound. Even if you are shown an isomorphism between two subgraphs of size n-1 (in graphs of size n), that does not guarantee the two graphs are isomorphic.
Joshua Grochow
CC BY-SA 3.0
2014-04-05T19:33:16.147Z
2014-04-05T19:40:33.520Z
2014-04-05T19:40:33.520Z
Marzio De Biasi
<p>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.</p>

CC BY-SA 3.0
2014-04-06T12:08:59.067Z
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.
Denis
CC BY-SA 3.0
2014-04-05T19:54:15.430Z
2014-04-05T19:54:15.430Z
David Monniaux
<p>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.</p>

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

<p>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 ? </p>

<graph-isomorphism>
graph isomorphism given a partial isomorphism
Denis
# graph isomorphism given a partial isomorphism

(Asked by: username_0 on 2014-04-05)

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 ?

**Tags:** graph-isomorphism

---

## 2 answers

### Answer by username_1 on 2014-04-05. Score: 8

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.](http://dl.acm.org/citation.cfm?id=793388) In Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity (COCO '99). IEEE Computer Society, Washington, DC, USA, 34-.

> **Comments:**
> **username_2**: Nice reference. Why is "Conference on Computational Complexity" abbreviated as COCO instead of CCC?  
> **username_1**: @HuckBennett: I copied/pasted the acm.org "ACM Ref" format (on the right of the dl.acm.org pages).  
> **username_2**: Yes, I was asking why it was abbreviated that way on the ACM page.  
> **username_1**: @HuckBennett: I think it was its original abbreviation ?!?  
> **username_3**: @HuckBennett: I don't know the actual history, but according to DBLP the abbreviation changed from CoCo to CCC in 2003: http://www.informatik.uni-trier.de/~ley/db/conf/coco/  
> **username_0**: Thanks, nice reference, although the approach is a little different.  
> **username_2**: @JoshuaGrochow: Thanks, I didn't realize that both the name and abbreviation had changed over time.  
> **username_4**: @JoshuaGrochow , Assume, graphs $G, H$ are not isomorphic, but there exists a partial isomorphism of $(3+\epsilon)\log n$ vertices, is there a chance, that the  algorithm based on Lipton's paper would  provide an isomorphsim?  
> **username_3**: @Jim: As far as I understand it, Lipton et al. would only yield an isomorphism if there *was* an isomorphism that extended the partial isomorphism. (Merely having an isomorphism between two subgraphs of size $(3+\epsilon)\log n)$ seems to not be enough...)  
> **username_3**: @Jim: Of course there is no such bound. Even if you are shown an isomorphism between two subgraphs of size n-1 (in graphs of size n), that does not guarantee the two graphs are isomorphic.  

---

### Answer by username_5 on 2014-04-05. Score: 0

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.

> **Comments:**
> **username_0**: 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.  

---

