Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
add comment

2 Answers 2

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

share|improve this answer
    
Nice reference. Why is "Conference on Computational Complexity" abbreviated as COCO instead of CCC? –  Huck Bennett Apr 5 at 19:44
    
@HuckBennett: I copied/pasted the acm.org "ACM Ref" format (on the right of the dl.acm.org pages). –  Marzio De Biasi Apr 5 at 19:51
    
Yes, I was asking why it was abbreviated that way on the ACM page. –  Huck Bennett Apr 5 at 19:57
    
@HuckBennett: I think it was its original abbreviation ?!? –  Marzio De Biasi Apr 5 at 20:01
2  
@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 –  Joshua Grochow Apr 6 at 3:59
show 2 more comments

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.

share|improve this answer
    
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 Apr 6 at 12:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.