Common subgraph isomorphism with K vertex

Question

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.

Answer 1

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.