TR-2018-03

VF2++ - An Improved Subgraph Isomorphism Algorithm

Alpár Jüttner, Péter Madarasi



Abstract

This paper presents a largely improved version of the VF2 algorithm for the Subgraph Isomorphism Problem. The improvements are twofold. Firstly, it is based on a new approach for determining the matching order of the nodes, and secondly, more efficient -- nevertheless easier to compute -- cutting rules are proposed. They together reduce the search space significantly.
 
In addition to the usual Subgraph Isomorphism Problem, the paper also presents specialized algorithms for the Induced Subgraph Isomorphism and for the Graph Isomorphism Problems.
 
Finally, an extensive experimental evaluation is provided using a wide range of inputs, including both real-life biological and chemical datasets and standard randomly generated graph series. The results show major and consistent running time improvements over the other known methods. The C++ implementations of the algorithms are available open-source as part of the LEMON graph and network optimization library.


Bibtex entry:

@techreport{egres-18-03,
AUTHOR = {Jüttner, Alp{\'a}r and Madarasi, P{\'e}ter},
TITLE = {VF2++ - An Improved Subgraph Isomorphism Algorithm},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2018},
NUMBER = {TR-2018-03}
}


Last modification: 29.12.2020. Please email your comments to Tamás Király!