5
$\begingroup$

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 ?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
8
$\begingroup$

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

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

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Denis
    Commented Apr 6, 2014 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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