Scoring-based Neighborhood Dominance for the Subgraph Isomorphism Problem
Gilles Audemard, Christophe Lecoutre, Mouny Samy-Modeliar, Gilles Gonçalves, Daniel Cosmin Porumbel · 2014
Abstract. This paper presents an original filtering approach, called SND (Scoring-based Neighborhood Dominance), for the subgraph isomorphism problem. By reasoning on vertex dominance properties based on various scoring and neigh-borhood functions, SND appears to be a filtering mechanism of strong inference potential. For example, the recently proposed method LAD is a particular case of SND. We study a specialization of SND by considering the number of k-length paths in graphs and three ways of relating sets of vertices. With this specializa-tion, we prove that SND is stronger than LAD and incomparable to SAC (Single-ton Arc Consistency). Our experimental results show that SND achieves most of the time the same filtering performances as SAC (while being several orders of magnitude faster), which allows one to find subisomorphism functions far more efficiently than MAC, while slightly outperforming LAD. 1