# 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

1. Is there any algorithm available for checking subgraph isomorphism in Multigraphs (specifically for multiple edge types) ?
2. If yes, what is the complexity?
• I don't really know much about this, but the topic of graph limits and graph convergence is related to counting the number of homomorphisms, so it might be something to look into. It's mathematical though, and so doesn't provide guidelines for actually finding the homomorphisms, but it might help by providing another angle to the problem. – Mederr Jul 19 '18 at 10:33
• And well, there is of course pattern-matching. Perhaps searching some stuff about that would give a more direct result, which you can then adjust to multigraphs :) – Mederr Jul 19 '18 at 10:39
• Subgraph isomorphism (for simple graphs) is already NP-complete. – Yuval Filmus Jul 19 '18 at 11:01