The Subgraph Similarity Problem
Laura De Nardo, Francesco Ranzato, Francesco Tapparo · IEEE Transactions on Knowledge and Data Engineering · 2008
Similarity is a well known weakening of bisimilarity where one system is required to simulate the other and vice versa. It has been shown that the subgraph bisimilarity problem, a variation of the subgraph isomorphism problem where isomorphism is weakened to bisimilarity, is NP-complete. We show that the subgraph similarity problem and some related variations thereof still remain NP-complete.