Subgraph Isomorphism checking in Multigraphs I am considering the following problem:

Input: 2 Graphs G=(V,E), H=(V',E'). G and H are directed multigraphs
Question: Find a subgraph in G which is isomorphic to H


Is there any algorithm available for checking subgraph isomorphism in Multigraphs (specifically for multiple edge types) ?
If yes, what is the complexity?
Submultigraph isomorphism is clearly NP complete:


it's easily seen to be in NP (an isomorphism can be specified in space polynomial in the size of the graphs, and it's easy to check that a proposed isomorphism is valid);
it includes the NP-complete subgraph isomorphism problem as a special case.


The more interesting question is what the best known algorithms are; I'm afraid I can't help with that.