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.