The VF3-light subgraph isomorphism algorithm: When doing less is more effective

We have recently intoduced VF3, a general-purpose subgraph isomorphism algorithm that has demonstrated to be very effective on several datasets, especially on very large and very dense graphs. In this paper we show that on some classes of graphs, the whole power of VF3 may become overkill; indeed, by removing some of the heuristics used in it, and as a consequence also some of the data structures that are required by them, we obtain an algorithm that is actually faster. In order to provide a characterization of this modified algorithm, called VF3-Light, we have performed an evaluation using several kinds of graphs; besides comparing VF3-Light with VF3, we have also compared it to RI, a fast recent algorithm that is based on a similar approach.