Re: [igraph] Graph isomorphism / maximum common subgraph

[Gábor Csárdi]

Hi Benjamin,

http://en.wikipedia.org/wiki/Maximum_common_subgraph_isomorphism_problem
says that a possible way to find the maximum common subgraph is to
create the modular product of the two graphs, which does not seem to
be very difficult, and the then find the maximum clique in this graph,
for which igraph has algorithms. (The implementation in the 0.6
version is much faster.)

Even if your graphs have only 200 vertices, this might be a difficult
thing to calculate, because already the modular product will have
about 200x200 vertices, and you need to find the largest clique in
these, which is an NP-complete problem (of course).

I am not sure what you mean about "most accurate", you are interested
in approximate solutions?

Best,
Gabor

On Mon, May 2, 2011 at 3:18 PM, Benjamin Wellmann <address@hidden> wrote:
> Hello igraph-help-list,
>
> I'm using python and I'm looking for a package that has algorithms to find the
>  'maximum common subgraph'/isomorphism 
> [http://en.wikipedia.org/wiki/Maximum_common_subgraph_isomorphism_problem] 
> between two graphs.
>
> I would expect that the method 'get_subisomorphisms_vf2' would help me, but 
> is there a possibility to limit the search to the largest (maximum) 
> isomorphism with the highest number of nodes.
>
> Furthermore, my graphs are not 'very huge' (max. 200 nodes), do you have any 
> hints which algorithm could be the most accurate?
>
> Thanks for any help
> Benjamin
>
>
>
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>



-- 
Gabor Csardi <address@hidden>     MTA KFKI RMKI