\title{VF2++ --- An Improved Subgraph Isomorphism Algorithm}

 \title{Improved Algorithms for Matching Biological Graphs}

 \author[egres,elte]{Alp{\'a}r J{\"u}ttner}

 \author{Alp{\'a}r J{\"u}ttner and P{\'e}ter Madarasi}

 \ead{alpar@cs.elte.hu}

 \author[elte]{P{\'e}ter Madarasi}

 \address{Dept of Operations Research, ELTE}

 \ead{madarasip@caesar.elte.hu}

 \address[egres]{MTA-ELTE Egerv{\'a}ry Research Group, Budapest, Hungary.}

 \address[elte]{Department of Operations Research, E{\"o}tv{\"o}s Lor{\'a}nd University, Budapest, Hungary.}

 Subgraph isomorphism is a well-known NP-Complete problem, while its

   This paper presents a largely improved version of the VF2 algorithm

 special case, the graph isomorphism problem is one of the few problems

   for the \emph{Subgraph Isomorphism Problem}. The improvements are

 in NP neither known to be in P nor NP-Complete. Their appearance in

   twofold. Firstly, it is based on a new approach for determining the

 many fields of application such as pattern analysis, computer vision

   matching order of the nodes, and secondly, more efficient -

 questions and the analysis of chemical and biological systems has

   nevertheless easier to compute - cutting rules significantly

 fostered the design of various algorithms for handling special graph

   reducing the search space are applied.

 structures.

   In addition to the usual subgraph isomorphism, the paper also

 This paper presents VF2++, a new algorithm based on the original VF2,

   presents specialized versions for the \emph{Induced Subgraph

 which runs significantly faster on most test cases and performs

     Isomorphism} and for the \emph{Graph Isomorphism Problems}.

 especially well on special graph classes stemming from biological

 questions. VF2++ handles graphs of thousands of nodes in practically

   Finally, an extensive experimental evaluation is provided using a

 near linear time including preprocessing. Not only is it an improved

   wide range of inputs, including both real life biological and

 version of VF2, but in fact, it is by far the fastest existing

   chemical datasets and standard randomly generated graph series. The

 algorithm especially on biological graphs.

   results show major and consistent running time improvements over the

   other known methods.

 The reason for VF2++' superiority over VF2 is twofold. Firstly, taking

 into account the structure and the node labeling of the graph, VF2++

   The C++ implementations of the algorithms are available open source as

 determines a state order in which most of the unfruitful branches of

   the part of the LEMON graph and network optimization library.

 the search space can be pruned immediately. Secondly, introducing more

 efficient - nevertheless still easier to compute - cutting rules

 reduces the chance of going astray even further.

 In addition to the usual subgraph isomorphism, specialized versions

 for induced subgraph isomorphism and for graph isomorphism are

 presented. VF2++ has gained a runtime improvement of one order of

 magnitude respecting induced subgraph isomorphism and a better

 asymptotical behaviour in the case of graph isomorphism problem.

 After having provided the description of VF2++, in order to evaluate

 its effectiveness, an extensive comparison to the contemporary other

 algorithms is shown, using a wide range of inputs, including both real

 life biological and chemical datasets and standard randomly generated

 graph series.

 The work was motivated and sponsored by QuantumBio Inc., and all the

 developed algorithms are available as the part of the open source

 LEMON graph and network optimization library

 (http://lemon.cs.elte.hu).

 requires finding specific subgraphs, thus calls for efficient

 requires finding specific subgraphs, thus it calls for efficient

 Inc.\cite{QUANTUMBIO} and the implementation --- along with a source

 Inc.\cite{QUANTUMBIO} and the implementation is available open source as the 

 code --- has been published as a part of LEMON\cite{LEMON} open source

 part of the LEMON\cite{LEMON} graph and network optimization library.

 graph library.

 Outline: Section~\ref{sec:ProbStat} defines the problems to be solved, Section~\ref{sec:VF2Alg} provides a description of VF2, Section~\ref{sec:VF2ppAlg} introduces VF2++, a new graph matching algorithm, Section~\ref{sec:VF2ppImpl} presents the details of an efficient implementation of VF2++, and Section~\ref{sec:ExpRes} compares VF2++ to the state of the art algorithm.

 Outline: Section~\ref{sec:ProbStat} defines the problems to be solved, Section~\ref{sec:VF2Alg} provides a description of VF2, Section~\ref{sec:VF2ppAlg} introduces VF2++, a new graph matching algorithm, Section~\ref{sec:VF2ppImpl} presents the details of an efficient implementation of VF2++, and Section~\ref{sec:ExpRes} compares VF2++ to a state of the art algorithm.