3
$\begingroup$

I'm looking for subgraph isomorphism of at least K vertex between Graph A and B. I only can come up with the dumbest algorithm, which is:

  • Compute all combination of vertices with length K of Graph A.
  • Run subgraph isomorphism test for every combination vertices against Graph B, probably using VF2 algorithm.

Upon researching I found Maximum Common Subgraph. On one paragraph, there is

The associated decision problem, i.e., given G1, G2 and an integer k, deciding whether G1 contains a subgraph of at least k vertices isomorphic to a subgraph of G2 is NP-complete.

This "associated decision problem" is exactly what I'm looking for. But I can't look further than this Wikipedia article to learn about it. Can anybody point me to related paper or text about this problem? Or even better, slightly explain to me how solution of the problem might works compared to my dumb algorithm.

My sincerest thank to you all.

$\endgroup$

migrated from cstheory.stackexchange.com Nov 18 '14 at 19:15

This question came from our site for theoretical computer scientists and researchers in related fields.

3
$\begingroup$

The fact that the Maximum Common Subgraph is NP-complete suggests that your "dumb" algorithm is about as good as it gets. You certainly cannot expect a polynomial time solution.

There are a few approaches you could try, depending on the exact context you are working in, the details of which are more than can reasonably be reproduced here, but a good starting point would be Abu-Khzam et al.'s paper "The Maximum Common Subgraph Problem: Faster Solutions via Vertex Cover" (In Proceedings of AICCSA 2007, pp. 367-373). This describes a variety of exact approaches which exploit different properties of the input.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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