0
$\begingroup$

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?
Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Mederr
    Commented Jul 19, 2018 at 10:33
  • $\begingroup$ 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 :) $\endgroup$
    – Mederr
    Commented Jul 19, 2018 at 10:39
  • $\begingroup$ Subgraph isomorphism (for simple graphs) is already NP-complete. $\endgroup$
    – Yuval Filmus
    Commented Jul 19, 2018 at 11:01

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

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.