vf2

VF2 is a graph matching algorithm used to determine subgraph isomorphism and, in some cases, graph isomorphism. It is part of the VF family of algorithms and was introduced by Cordella, Foggia, Sansone, and Vento. The method is designed to be efficient in practice by combining a depth-first search with strong pruning rules and a dynamic candidate selection strategy.

The problem it addresses involves two graphs: a pattern graph P and a target graph G. The goal is to find an injective mapping from the vertices of P to the vertices of G that preserves adjacency and labeling, so that P is contained within G as a subgraph, or to determine a complete correspondence if the graphs are of equal size. VF2 represents the current partial correspondence with a mapping and its inverse, and it maintains a set of candidate target vertices for extension. At each step, VF2 selects a pattern vertex to map next, typically choosing one with the fewest feasible candidates to reduce branching.

Feasibility checks are central to VF2’s pruning. A proposed pair (u, v) of pattern vertex u and target vertex v is considered feasible if: the labels on u and v match (and any relevant edge labels align); the degrees and neighborhood structure of u are compatible with those of v given the already mapped vertices; and for every already mapped neighbor u' of u, there is a corresponding edge to the mapped vertex v' of v. If the pair passes these checks, the mapping is extended; otherwise backtracking occurs. The search continues until a complete mapping is found (for subgraph isomorphism, mapping all of P) or all possibilities are exhausted.

VF2 is widely used in domains such as cheminformatics, pattern recognition, and graph databases due to its balance of pruning efficiency and general applicability to directed or undirected, labeled graphs.