%% 

 %% Copyright 2007, 2008, 2009 Elsevier Ltd

 %% 

 %% This file is part of the 'Elsarticle Bundle'.

 %% ---------------------------------------------

 %% 

 %% It may be distributed under the conditions of the LaTeX Project Public

 %% License, either version 1.2 of this license or (at your option) any

 %% later version.  The latest version of this license is in

 %%    http://www.latex-project.org/lppl.txt

 %% and version 1.2 or later is part of all distributions of LaTeX

 %% version 1999/12/01 or later.

 %% 

 %% The list of all files belonging to the 'Elsarticle Bundle' is

 %% given in the file `manifest.txt'.

 %% 

 %% Template article for Elsevier's document class `elsarticle'

 %% with numbered style bibliographic references

 %% SP 2008/03/01

 \documentclass[preprint,12pt]{elsarticle}

 %% Use the option review to obtain double line spacing

 %% \documentclass[authoryear,preprint,review,12pt]{elsarticle}

 %% Use the options 1p,twocolumn; 3p; 3p,twocolumn; 5p; or 5p,twocolumn

 %% for a journal layout:

 %% \documentclass[final,1p,times]{elsarticle}

 %% \documentclass[final,1p,times,twocolumn]{elsarticle}

 %% \documentclass[final,3p,times]{elsarticle}

 %% \documentclass[final,3p,times,twocolumn]{elsarticle}

 %% \documentclass[final,5p,times]{elsarticle}

 %% \documentclass[final,5p,times,twocolumn]{elsarticle}

 %% For including figures, graphicx.sty has been loaded in

 %% elsarticle.cls. If you prefer to use the old commands

 %% please give \usepackage{epsfig}

 %% The amssymb package provides various useful mathematical symbols

 \usepackage{amssymb}

 %% The amsthm package provides extended theorem environments

 %% \usepackage{amsthm}

 %% The lineno packages adds line numbers. Start line numbering with

 %% \begin{linenumbers}, end it with \end{linenumbers}. Or switch it on

 %% for the whole article with \linenumbers.

 %% \usepackage{lineno}

 \usepackage{amsmath}

 %% \usepackage[pdftex]{graphicx}

 \usepackage{pgfplots}

 \pgfplotsset{width=9cm}

 \pgfplotsset{compat=1.8}

 \usepackage{caption}

 \usepackage{subcaption} 

 \usepackage{algorithm}

 \usepackage{algpseudocode}

 \usepackage{tikz}

 \usepackage{amsthm,amssymb}

 \renewcommand{\qedsymbol}{\rule{0.7em}{0.7em}}

 \newtheorem{theorem}{Theorem}[subsection]

 \newtheorem{corollary}{Corollary}[theorem]

 \newtheorem{claim}[theorem]{Claim}

 \newtheorem{definition}{Definition}[subsection]

 \newtheorem{notation}{Notation}[subsection]

 \newtheorem{example}{Example}[subsection]

 \usetikzlibrary{decorations.markings}

 \let\oldproofname=\proofname

 %% \renewcommand{\proofname}{\rm\bf{Proof:}}

 \captionsetup{font=normalsize}

 \journal{Discrete Applied Mathematics}

 \begin{document}

 \begin{frontmatter}

 %% Title, authors and addresses

 %% use the tnoteref command within \title for footnotes;

 %% use the tnotetext command for theassociated footnote;

 %% use the fnref command within \author or \address for footnotes;

 %% use the fntext command for theassociated footnote;

 %% use the corref command within \author for corresponding author footnotes;

 %% use the cortext command for theassociated footnote;

 %% use the ead command for the email address,

 %% and the form \ead[url] for the home page:

 %% \title{Title\tnoteref{label1}}

 %% \tnotetext[label1]{}

 %% \author{Name\corref{cor1}\fnref{label2}}

 %% \ead{email address}

 %% \ead[url]{home page}

 %% \fntext[label2]{}

 %% \cortext[cor1]{}

 %% \address{Address\fnref{label3}}

 %% \fntext[label3]{}

 \title{Improved Algorithms for Matching Biological Graphs}

 %% use optional labels to link authors explicitly to addresses:

 %% \author[label1,label2]{}

 %% \address[label1]{}

 %% \address[label2]{}

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

 \address{Dept of Operations Research, ELTE}

 \begin{abstract}

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

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

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

 many fields of application such as pattern analysis, computer vision

 questions and the analysis of chemical and biological systems has

 fostered the design of various algorithms for handling special graph

 structures.

 The idea of using state space representation and checking some

 conditions in each state to prune the search tree has made the VF2

 algorithm one of the state of the art graph matching algorithms for

 more than a decade. Recently, biological questions of ever increasing

 importance have required more efficient, specialized algorithms.

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

 which runs significantly faster on most test cases and performs

 especially well on special graph classes stemming from biological

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

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

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

 algorithm regarding biological graphs.

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

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

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

 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).

 \end{abstract}

 \begin{keyword}

 %% keywords here, in the form: keyword \sep keyword

 %% PACS codes here, in the form: \PACS code \sep code

 %% MSC codes here, in the form: \MSC code \sep code

 %% or \MSC[2008] code \sep code (2000 is the default)

 \end{keyword}

 \end{frontmatter}

 %% \linenumbers

 %% main text

 \section{Introduction}

 \label{sec:intro}

 In the last decades, combinatorial structures, and especially graphs

 have been considered with ever increasing interest, and applied to the

 solution of several new and revised questions.  The expressiveness,

 the simplicity and the studiedness of graphs make them practical for

 modelling and appear constantly in several seemingly independent

 fields.  Bioinformatics and chemistry are amongst the most relevant

 and most important fields.

 Complex biological systems arise from the interaction and cooperation

 of plenty of molecular components. Getting acquainted with such

 systems at the molecular level has primary importance, since

 protein-protein interaction, DNA-protein interaction, metabolic

 interaction, transcription factor binding, neuronal networks, and

 hormone signaling networks can be understood only this way.

 For instance, a molecular structure can be considered as a graph,

 whose nodes correspond to atoms and whose edges to chemical bonds. The

 secondary structure of a protein can also be represented as a graph,

 where nodes are associated with aminoacids and the edges with hydrogen

 bonds. The nodes are often whole molecular components and the edges

 represent some relationships among them.  The similarity and

 dissimilarity of objects corresponding to nodes are incorporated to

 the model by \emph{node labels}.  Many other chemical and biological

 structures can easily be modeled in a similar way. Understanding such

 networks basically requires finding specific subgraphs, which can not

 avoid the application of graph matching algorithms.

 Finally, let some of the other real-world fields related to some

 variants of graph matching be briefly mentioned: pattern recognition

 and machine vision \cite{HorstBunkeApplications}, symbol recognition

 \cite{CordellaVentoSymbolRecognition}, face identification

 \cite{JianzhuangYongFaceIdentification}.  \\

 Subgraph and induced subgraph matching problems are known to be

 NP-Complete\cite{SubgraphNPC}, while the graph isomorphism problem is

 one of the few problems in NP neither known to be in P nor

 NP-Complete. Although polynomial time isomorphism algorithms are known

 for various graph classes, like trees and planar

 graphs\cite{PlanarGraphIso}, bounded valence

 graphs\cite{BondedDegGraphIso}, interval graphs\cite{IntervalGraphIso}

 or permutation graphs\cite{PermGraphIso}.

 In the following, some algorithms based on other approaches are

 summarized, which do not need any restrictions on the graphs. However,

 an overall polynomial behaviour is not expectable from such an

 alternative, it may often have good performance, even on a graph class

 for which polynomial algorithm is known. Note that this summary

 containing only exact matching algorithms is far not complete, neither

 does it cover all the recent algorithms.

 The first practically usable approach was due to

 Ullmann\cite{Ullmann} which is a commonly used depth-first

 search based algorithm with a complex heuristic for reducing the

 number of visited states. A major problem is its $\Theta(n^3)$ space

 complexity, which makes it impractical in the case of big sparse

 graphs.

 In a recent paper, Ullmann\cite{UllmannBit} presents an

 improved version of this algorithm based on a bit-vector solution for

 the binary Constraint Satisfaction Problem.

 The Nauty algorithm\cite{Nauty} transforms the two graphs to

 a canonical form before starting to check for the isomorphism. It has

 been considered as one of the fastest graph isomorphism algorithms,

 although graph categories were shown in which it takes exponentially

 many steps. This algorithm handles only the graph isomorphism problem.

 The \emph{LAD} algorithm\cite{Lad} uses a depth-first search

 strategy and formulates the matching as a Constraint Satisfaction

 Problem to prune the search tree. The constraints are that the mapping

 has to be injective and edge-preserving, hence it is possible to

 handle new matching types as well.

 The \textbf{RI} algorithm\cite{RI} and its variations are based on a

 state space representation. After reordering the nodes of the graphs,

 it uses some fast executable heuristic checks without using any

 complex pruning rules. It seems to run really efficiently on graphs

 coming from biology, and won the International Contest on Pattern

 Search in Biological Databases\cite{Content}.

 The currently most commonly used algorithm is the

 \textbf{VF2}\cite{VF2}, the improved version of VF\cite{VF}, which was

 designed for solving pattern matching and computer vision problems,

 and has been one of the best overall algorithms for more than a

 decade. Although, it can't be up to new specialized algorithms, it is

 still widely used due to its simplicity and space efficiency. VF2 uses

 a state space representation and checks some conditions in each state

 to prune the search tree.

 Our first graph matching algorithm was the first version of VF2 which

 recognizes the significance of the node ordering, more opportunities

 to increase the cutting efficiency and reduce its computational

 complexity. This project was initiated and sponsored by QuantumBio

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

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

 graph library.

 This paper introduces \textbf{VF2++}, a new further improved algorithm

 for the graph and (induced)subgraph isomorphism problem, which uses

 efficient cutting rules and determines a node order in which VF2 runs

 significantly faster on practical inputs.

 Meanwhile, another variant called \textbf{VF2 Plus}\cite{VF2Plus} has

 been published. It is considered to be as efficient as the RI

 algorithm and has a strictly better behavior on large graphs.  The

 main idea of VF2 Plus is to precompute a heuristic node order of the

 small graph, in which the VF2 works more efficiently.

 \section{Problem Statement}

 This section provides a detailed description of the problems to be

 solved.

 \subsection{Definitions}

 Throughout the paper $G_{small}=(V_{small}, E_{small})$ and

 $G_{large}=(V_{large}, E_{large})$ denote two undirected graphs.

 \begin{definition}\label{sec:ismorphic}

 $G_{small}$ and $G_{large}$ are \textbf{isomorphic} if $\exists M:

   V_{small} \longrightarrow V_{large}$ bijection, for which the

   following is true:

 \begin{center}

 $\forall u,v\in{V_{small}} : (u,v)\in{E_{small}} \Leftrightarrow

   (M(u),M(v))\in{E_{large}}$

 \end{center}

 \end{definition}

 For the sake of simplicity in this paper subgraphs and induced

 subgraphs are defined in a more general way than usual:

 \begin{definition}

 $G_{small}$ is a \textbf{subgraph} of $G_{large}$ if $\exists I:

   V_{small}\longrightarrow V_{large}$ injection, for which the

   following is true:

 \begin{center}

 $\forall u,v \in{V_{small}} : (u,v)\in{E_{small}} \Rightarrow (I(u),I(v))\in E_{large}$

 \end{center}

 \end{definition}

 \begin{definition} 

 $G_{small}$ is an \textbf{induced subgraph} of $G_{large}$ if $\exists

   I: V_{small}\longrightarrow V_{large}$ injection, for which the

   following is true:

 \begin{center}

 $\forall u,v \in{V_{small}} : (u,v)\in{E_{small}} \Leftrightarrow

   (I(u),I(v))\in E_{large}$

 \end{center}

 \end{definition}

 \begin{definition}

 $lab: (V_{small}\cup V_{large}) \longrightarrow K$ is a \textbf{node

     label function}, where K is an arbitrary set. The elements in K

   are the \textbf{node labels}. Two nodes, u and v are said to be

   \textbf{equivalent}, if $lab(u)=lab(v)$.

 \end{definition}

 When node labels are also given, the matched nodes must have the same

 labels.  For example, the node labeled isomorphism is phrased by

 \begin{definition}

 $G_{small}$ and $G_{large}$ are \textbf{isomorphic by the node label

     function lab} if $\exists M: V_{small} \longrightarrow V_{large}$

   bijection, for which the following is true:

 \begin{center}

 $(\forall u,v\in{V_{small}} : (u,v)\in{E_{small}} \Leftrightarrow

   (M(u),M(v))\in{E_{large}})$ and $(\forall u\in{V_{small}} :

   lab(u)=lab(M(u)))$

 \end{center}

 \end{definition}

 The other two definitions can be extended in the same way.

 Note that edge label function can be defined similarly to node label

 function, and all the definitions can be extended with additional

 conditions, but it is out of the scope of this work.

 The equivalence of two nodes is usually defined by another relation,

 $\\R\subseteq (V_{small}\cup V_{large})^2$. This overlaps with the

 definition given above if R is an equivalence relation, which does not

 mean restriction in biological and chemical applications.

 \subsection{Common problems}\label{sec:CommProb}

 The focus of this paper is on two extensively studied topics, the

 subgraph isomorphism and its variations. However, the following

 problems also appear in many applications.

 The \textbf{subgraph matching problem} is the following: is

 $G_{small}$ isomorphic to any subgraph of $G_{large}$ by a given node

 label?

 The \textbf{induced subgraph matching problem} asks the same about the

 existence of an induced subgraph.

 The \textbf{graph isomorphism problem} can be defined as induced

 subgraph matching problem where the sizes of the two graphs are equal.

 In addition to existence, it may be needed to show such a subgraph, or

 it may be necessary to list all of them.

 It should be noted that some authors misleadingly refer to the term

 \emph{subgraph isomorphism problem} as an \emph{induced subgraph

   isomorphism problem}.

 The following sections give the descriptions of VF2, VF2++, VF2 Plus

 and a particular comparison.

 \section{The VF2 Algorithm}

 This algorithm is the basis of both the VF2++ and the VF2 Plus.  VF2

 is able to handle all the variations mentioned in Section

   \ref{sec:CommProb}.  Although it can also handle directed graphs,

 for the sake of simplicity, only the undirected case will be

 discussed.

 \subsection{Common notations}

 \indent Assume $G_{small}$ is searched in $G_{large}$.  The following

 definitions and notations will be used throughout the whole paper.

 \begin{definition}

 A set $M\subseteq V_{small}\times V_{large}$ is called

 \textbf{mapping}, if no node of $V_{small}$ or of $V_{large}$ appears

 in more than one pair in M.  That is, M uniquely associates some of

 the nodes in $V_{small}$ with some nodes of $V_{large}$ and vice

 versa.

 \end{definition}

 \begin{definition}

 Mapping M \textbf{covers} a node v, if there exists a pair in M, which

 contains v.

 \end{definition}

 \begin{definition}

 A mapping $M$ is $\mathbf{whole\ mapping}$, if $M$ covers all the

 nodes in $V_{small}$.

 \end{definition}

 \begin{notation}

 Let $\mathbf{M_{small}(s)} := \{u\in V_{small} : \exists v\in

 V_{large}: (u,v)\in M(s)\}$ and $\mathbf{M_{large}(s)} := \{v\in

 V_{large} : \exists u\in V_{small}: (u,v)\in M(s)\}$.

 \end{notation}

 \begin{notation}

 Let $\mathbf{Pair(M,v)}$ be the pair of $v$ in $M$, if such a node

 exist, otherwise $\mathbf{Pair(M,v)}$ is undefined. For a mapping $M$

 and $v\in V_{small}\cup V_{large}$.

 \end{notation}

 Note that if $\mathbf{Pair(M,v)}$ exists, then it is unique

 The definitions of the isomorphism types can be rephrased on the

 existence of a special whole mapping $M$, since it represents a

 bijection. For example

 \begin{center}

 $M\subseteq V_{small}\times V_{large}$ represents an induced subgraph

   isomorphism $\Leftrightarrow$ $M$ is whole mapping and $\forall u,v

   \in{V_{small}} : (u,v)\in{E_{small}} \Leftrightarrow

   (Pair(M,u),Pair(M,v))\in E_{large}$.

 \end{center}

 \begin{definition}

 A set of whole mappings is called \textbf{problem type}.

 \end{definition}

 Throughout the paper, $\mathbf{PT}$ denotes a generic problem type

 which can be substituted by any problem type.

 A whole mapping $W\mathbf{\ is\ of\ type\ PT}$, if $W\in PT$. Using

 this notations, VF2 searches a whole mapping $W$ of type $PT$.

 For example the problem type of graph isomorphism problem is the

 following.  A whole mapping $W$ is in $\mathbf{ISO}$, iff the

 bijection represented by $W$ satisfies Definition~\ref{sec:ismorphic}.

 The subgraph- and induced subgraph matching problems can be formalized

 in a similar way. Let their problem types be denoted as $\mathbf{SUB}$

 and $\mathbf{IND}$.

 \begin{definition}

 \label{expPT}

 $PT$ is an \textbf{expanding problem type} if $\ \forall\ W\in

 PT:\ \forall u_1,u_2\in V_{small}:\ (u_1,u_2)\in E_{small}\Rightarrow

 (Pair(W,u_1),Pair(W,u_2))\in E_{large}$, that is each edge of

 $G_{small}$ has to be mapped to an edge of $G_{large}$ for each

 mapping in $PT$.

 \end{definition}

 Note that $ISO$, $SUB$ and $IND$ are expanding problem types.

 This paper deals with the three problem types mentioned above only,

 but the following generic definitions make it possible to handle other

 types as well.  Although it may be challenging to find a proper

 consistency function and an efficient cutting function.

 \begin{definition}

 Let M be a mapping. A logical function $\mathbf{Cons_{PT}}$ is a

 \textbf{consistency function by } $\mathbf{PT}$, if the following

 holds. If there exists whole mapping $W$ of type PT for which

 $M\subseteq W$, then $Cons_{PT}(M)$ is true.

 \end{definition}

 \begin{definition} 

 Let M be a mapping. A logical function $\mathbf{Cut_{PT}}$ is a

 \textbf{cutting function by } $\mathbf{PT}$, if the following

 holds. $\mathbf{Cut_{PT}(M)}$ is false if $M$ can be extended to a

 whole mapping W of type PT.

 \end{definition}

 \begin{definition}

 $M$ is said to be \textbf{consistent mapping by} $\mathbf{PT}$, if

   $Cons_{PT}(M)$ is true.

 \end{definition}

 $Cons_{PT}$ and $Cut_{PT}$ will often be used in the following form.

 \begin{notation}

 Let $\mathbf{Cons_{PT}(p, M)}:=Cons_{PT}(M\cup\{p\})$ and

 $\mathbf{Cut_{PT}(p, M)}:=Cut_{PT}(M\cup\{p\})$, where

 $p\in{V_{small}\!\times\!V_{large}}$ and $M\cup\{p\}$ is mapping.

 \end{notation}

 $Cons_{PT}$ will be used to check the consistency of the already

 covered nodes, while $Cut_{PT}$ is for looking ahead to recognize if

 no whole consistent mapping can contain the current mapping.

 \subsection{Overview of the algorithm}

 VF2 uses a state space representation of mappings, $Cons_{PT}$ for

 excluding inconsistency with the problem type and $Cut_{PT}$ for

 pruning the search tree.  Each state $s$ of the matching process can

 be associated with a mapping $M(s)$.

 Algorithm~\ref{alg:VF2Pseu} is a high level description of

 the VF2 matching algorithm.

 \begin{algorithm}

 \algtext*{EndIf}%ne nyomtasson end if-et

 \algtext*{EndFor}%ne

 \algtext*{EndProcedure}%ne nyomtasson ..

 \caption{\hspace{0.5cm}$A\ high\ level\ description\ of\ VF2$}\label{alg:VF2Pseu}

 \begin{algorithmic}[1]

 \Procedure{VF2}{State $s$, ProblemType $PT$} \If{$M(s$) covers

   $V_{small}$} \State Output($M(s)$) \Else

   \State Compute the set $P(s)$ of the pairs candidate for inclusion

   in $M(s)$ \ForAll{$p\in{P(s)}$} \If{Cons$_{PT}$($p, M(s)$) $\wedge$

     $\neg$Cut$_{PT}$($p, M(s)$)} \State Compute the nascent state

   $\tilde{s}$ by adding $p$ to $M(s)$ \State \textbf{call}

   VF2($\tilde{s}$, $PT$) \EndIf \EndFor \EndIf \EndProcedure

 \end{algorithmic}

 \end{algorithm}

 The initial state $s_0$ is associated with $M(s_0)=\emptyset$, i.e. it

 starts with an empty mapping.

 For each state $s$, the algorithm computes $P(s)$, the set of

 candidate node pairs for adding to the current state $s$.

 For each pair $p$ in $P(s)$, $Cons_{PT}(p,M(s))$ and

 $Cut_{PT}(p,M(s))$ are evaluated. If $Cons_{PT}(p,M(s))$ is true and

 $Cut_{PT}(p,M(s))$ is false, the successor state $\tilde{s}=s\cup

 \{p\}$ is computed, and the whole process is recursively applied to

 $\tilde{s}$. Otherwise, $\tilde{s}$ is not consistent by $PT$ or it

 can be proved that $s$ can not be extended to a whole mapping.

 In order to make sure of the correctness, see

 \begin{claim}

 Through consistent mappings, only consistent whole mappings can be

 reached, and all of the whole mappings are reachable through

 consistent mappings.

 \end{claim}

 Note that a state may be reached in many different ways, since the

 order of insertions into M does not influence the nascent mapping. In

 fact, the number of different ways which lead to the same state can be

 exponentially large. If $G_{small}$ and $G_{large}$ are circles with n

 nodes and n different node labels, there exists exactly one graph

 isomorphism between them, but it will be reached in $n!$ different

 ways.

 However, one may observe

 \begin{claim}

 \label{claim:claimTotOrd}

 Let $\prec$ an arbitrary total ordering relation on $V_{small}$.  If

 the algorithm ignores each $p=(u,v) \in P(s)$, for which

 \begin{center}

 $\exists (\hat{u},\hat{v})\in P(s): \hat{u} \prec u$,

 \end{center}

 then no state can be reached more than ones and each state associated

 with a whole mapping remains reachable.

 \end{claim}

 Note that the cornerstone of the improvements to VF2 is a proper

 choice of a total ordering.

 \subsection{The candidate set P(s)}

 \label{candidateComputingVF2}

 $P(s)$ is the set of the candidate pairs for inclusion in $M(s)$.

 Suppose that $PT$ is an expanding problem type, see

 Definition~\ref{expPT}.

 \begin{notation}

 Let $\mathbf{T_{small}(s)}:=\{u \in V_{small} : u$ is not covered by

 $M(s)\wedge\exists \tilde{u}\in{V_{small}: (u,\tilde{u})\in E_{small}}

 \wedge \tilde{u}$ is covered by $M(s)\}$, and

 \\ $\mathbf{T_{large}(s)}\!:=\!\{v \in\!V_{large}\!:\!v$ is not

 covered by

 $M(s)\wedge\!\exists\tilde{v}\!\in\!{V_{large}\!:\!(v,\tilde{v})\in\!E_{large}}

 \wedge \tilde{v}$ is covered by $M(s)\}$

 \end{notation}

 The set $P(s)$ includes the pairs of uncovered neighbours of covered

 nodes and if there is not such a node pair, all the pairs containing

 two uncovered nodes are added. Formally, let

 \[

  P(s)\!=\!

   \begin{cases} 

    T_{small}(s)\times T_{large}(s)&\hspace{-0.15cm}\text{if }

    T_{small}(s)\!\neq\!\emptyset\!\wedge\!T_{large}(s)\!\neq

    \emptyset,\\ (V_{small}\!\setminus\!M_{small}(s))\!\times\!(V_{large}\!\setminus\!M_{large}(s))

    &\hspace{-0.15cm}otherwise.

   \end{cases}

 \]

 \subsection{Consistency}

 This section defines the consistency functions for the different

 problem types mentioned in Section~\ref{sec:CommProb}.

 \begin{notation}

 Let $\mathbf{\Gamma_{small} (u)}:=\{\tilde{u}\in V_{small} :

 (u,\tilde{u})\in E_{small}\}$\\ Let $\mathbf{\Gamma_{large}

   (v)}:=\{\tilde{v}\in V_{large} : (v,\tilde{v})\in E_{large}\}$

 \end{notation}

 Suppose $p=(u,v)$, where $u\in V_{small}$ and $v\in V_{large}$, $s$ is

 a state of the matching procedure, $M(s)$ is consistent mapping by

 $PT$ and $lab(u)=lab(v)$.  $Cons_{PT}(p,M(s))$ checks whether

 including pair $p$ into $M(s)$ leads to a consistent mapping by $PT$.

 \subsubsection{Induced subgraph isomorphism}

 $M(s)\cup \{(u,v)\}$ is a consistent mapping by $IND$ $\Leftrightarrow

 (\forall \tilde{u}\in M_{small}: (u,\tilde{u})\in E_{small}

 \Leftrightarrow (v,Pair(M(s),\tilde{u}))\in E_{large})$.\newline The

 following formulation gives an efficient way of calculating

 $Cons_{IND}$.

 \begin{claim}

 $Cons_{IND}((u,v),M(s)):=(\forall \tilde{v}\in \Gamma_{large}(v)

   \ \cap\ M_{large}(s):\\(Pair(M(s),\tilde{v}),u)\in E_{small})\wedge

   (\forall \tilde{u}\in \Gamma_{small}(u)

   \ \cap\ M_{small}(s):(v,Pair(M(s),\tilde{u}))\in E_{large})$ is a

   consistency function in the case of $IND$.

 \end{claim}

 \subsubsection{Graph isomorphism}

 $M(s)\cup \{(u,v)\}$ is a consistent mapping by $ISO$

 $\Leftrightarrow$ $M(s)\cup \{(u,v)\}$ is a consistent mapping by

 $IND$.

 \begin{claim}

 $Cons_{ISO}((u,v),M(s))$ is a consistency function by $ISO$ if and

   only if it is a consistency function by $IND$.

 \end{claim}

 \subsubsection{Subgraph isomorphism}

 $M(s)\cup \{(u,v)\}$ is a consistent mapping by $SUB$ $\Leftrightarrow

 (\forall \tilde{u}\in M_{small}:\\(u,\tilde{u})\in E_{small}

 \Rightarrow (v,Pair(M(s),\tilde{u}))\in E_{large})$.

 \newline

 The following formulation gives an efficient way of calculating

 $Cons_{SUB}$.

 \begin{claim}

 $Cons_{SUB}((u,v),M(s)):= (\forall \tilde{u}\in \Gamma_{small}(u)

   \ \cap\ M_{small}(s):\\(v,Pair(M(s),\tilde{u}))\in E_{large})$ is a

   consistency function by $SUB$.

 \end{claim}

 \subsection{Cutting rules}

 $Cut_{PT}(p,M(s))$ is defined by a collection of efficiently

 verifiable conditions. The requirement is that $Cut_{PT}(p,M(s))$ can

 be true only if it is impossible to extended $M(s)\cup \{p\}$ to a

 whole mapping.

 \begin{notation}

 Let $\mathbf{\tilde{T}_{small}}(s):=(V_{small}\backslash

 M_{small}(s))\backslash T_{small}(s)$, and

 \\ $\mathbf{\tilde{T}_{large}}(s):=(V_{large}\backslash

 M_{large}(s))\backslash T_{large}(s)$.

 \end{notation}

 \subsubsection{Induced subgraph isomorphism}

 \begin{claim}

 $Cut_{IND}((u,v),M(s)):= |\Gamma_{large} (v)\ \cap\ T_{large}(s)| <

   |\Gamma_{small} (u)\ \cap\ T_{small}(s)| \vee |\Gamma_{large}(v)\cap

   \tilde{T}_{large}(s)| < |\Gamma_{small}(u)\cap

   \tilde{T}_{small}(s)|$ is a cutting function by $IND$.

 \end{claim}

 \subsubsection{Graph isomorphism}

 Note that the cutting function of induced subgraph isomorphism defined

 above is a cutting function by $ISO$, too, however it is less

 efficient than the following while their computational complexity is

 the same.

 \begin{claim}

 $Cut_{ISO}((u,v),M(s)):= |\Gamma_{large} (v)\ \cap\ T_{large}(s)| \neq

   |\Gamma_{small} (u)\ \cap\ T_{small}(s)| \vee |\Gamma_{large}(v)\cap

   \tilde{T}_{large}(s)| \neq |\Gamma_{small}(u)\cap

   \tilde{T}_{small}(s)|$ is a cutting function by $ISO$.

 \end{claim}

 \subsubsection{Subgraph isomorphism}

 \begin{claim}

 $Cut_{SUB}((u,v),M(s)):= |\Gamma_{large} (v)\ \cap\ T_{large}(s)| <

   |\Gamma_{small} (u)\ \cap\ T_{small}(s)|$ is a cutting function by

   $SUB$.

 \end{claim}

 Note that there is a significant difference between induced and

 non-induced subgraph isomorphism:

 \begin{claim}

 \label{claimSUB}

 $Cut_{SUB}'((u,v),M(s)):= |\Gamma_{large} (v)\ \cap\ T_{large}(s)| <

 |\Gamma_{small} (u)\ \cap\ T_{small}(s)| \vee |\Gamma_{large}(v)\cap

 \tilde{T}_{large}(s)| < |\Gamma_{small}(u)\cap \tilde{T}_{small}(s)|$

 is \textbf{not} a cutting function by $SUB$.

 \end{claim}

 \section{The VF2++ Algorithm}

 Although any total ordering relation makes the search space of VF2 a

 tree, its choice turns out to dramatically influence the number of

 visited states. The goal is to determine an efficient one as quickly

 as possible.

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

 taking into account the structure and the node labeling of the graph,

 VF2++ determines a state order in which most of the unfruitful

 branches of 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 have been

 designed. 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.

 Note that a weaker version of the cutting rules and the more efficient

 candidate set calculating were described in \cite{VF2Plus}, too.

 It should be noted that all the methods described in this section are

 extendable to handle directed graphs and edge labels as well.

 The basic ideas and the detailed description of VF2++ are provided in

 the following.

 \subsection{Preparations}

 \begin{claim}

 \label{claim:claimCoverFromLeft}

 The total ordering relation uniquely determines a node order, in which

 the nodes of $V_{small}$ will be covered by VF2. From the point of

 view of the matching procedure, this means, that always the same node

 of $G_{small}$ will be covered on the d-th level.

 \end{claim}

 \begin{definition}

 An order $(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$ of

 $V_{small}$ is \textbf{matching order}, if exists $\prec$ total

 ordering relation, s.t. the VF2 with $\prec$ on the d-th level finds

 pair for $u_{\sigma(d)}$ for all $d\in\{1,..,|V_{small}|\}$.

 \end{definition}

 \begin{claim}\label{claim:MOclaim}

 A total ordering is matching order, iff the nodes of every component

 form an interval in the node sequence, and every node connects to a

 previous node in its component except the first node of the

 component. The order of the components is arbitrary.  \\Formally

 spoken, an order

 $(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$ of

 $V_{small}$ is matching order $\Leftrightarrow$ $\forall

 G'_{small}=(V'_{small},E'_{small})\ component\ of\ G_{small}: \forall

 i: (\exists j : j<i\wedge u_{\sigma(j)},u_{\sigma(i)}\in

 V'_{small})\Rightarrow \exists k : k < i \wedge (\forall l: k\leq

 l\leq i \Rightarrow u_{l}\in V'_{small}) \wedge

 (u_{\sigma{(k)}},u_{\sigma{(i)}})\in E'_{small}$, where $i,j,k,l\in

 \{1,..,|V_{small}|\}$\newline

 \end{claim}

 To summing up, a total ordering always uniquely determines a matching

 order, and every matching order can be determined by a total ordering,

 however, more than one different total orderings may determine the

 same matching order.

 \subsection{Idea behind the algorithm}

 The goal is to find a matching order in which the algorithm is able to

 recognize inconsistency or prune the infeasible branches on the

 highest levels and goes deep only if it is needed.

 \begin{notation}

 Let $\mathbf{Conn_{H}(u)}:=|\Gamma_{small}(u)\cap H\}|$, that is the

 number of neighbours of u which are in H, where $u\in V_{small} $ and

 $H\subseteq V_{small}$.

 \end{notation}

 The principal question is the following. Suppose a state $s$ is

 given. For which node of $T_{small}(s)$ is the hardest to find a

 consistent pair in $G_{large}$? The more covered neighbours a node in

 $T_{small}(s)$ has --- i.e. the largest $Conn_{M_{small}(s)}$ it has

 ---, the more rarely satisfiable consistency constraints for its pair

 are given.

 In biology, most of the graphs are sparse, thus several nodes in

 $T_{small}(s)$ may have the same $Conn_{M_{small}(s)}$, which makes

 reasonable to define a secondary and a tertiary order between them.

 The observation above proves itself to be as determining, that the

 secondary ordering prefers nodes with the most uncovered neighbours

 among which have the same $Conn_{M_{small}(s)}$ to increase

 $Conn_{M_{small}(s)}$ of uncovered nodes so much, as possible.  The

 tertiary ordering prefers nodes having the rarest uncovered labels.

 Note that the secondary ordering is the same as the ordering by $deg$,

 which is a static data in front of the above used.

 These rules can easily result in a matching order which contains the

 nodes of a long path successively, whose nodes may have low $Conn$ and

 is easily matchable into $G_{large}$. To avoid that, a BFS order is

 used, which provides the shortest possible paths.

 \newline

 In the following, some examples on which the VF2 may be slow are

 described, although they are easily solvable by using a proper

 matching order.

 \begin{example}

 Suppose $G_{small}$ can be mapped into $G_{large}$ in many ways

 without node labels. Let $u\in V_{small}$ and $v\in V_{large}$.

 \newline

 $lab(u):=black$

 \newline

 $lab(v):=black$

 \newline

 $lab(\tilde{u}):=red \ \forall \tilde{u}\in (V_{small}\backslash

 \{u\})$

 \newline

 $lab(\tilde{v}):=red \ \forall \tilde{v}\in (V_{large}\backslash

 \{v\})$

 \newline

 Now, any mapping by the node label $lab$ must contain $(u,v)$, since

 $u$ is black and no node in $V_{large}$ has a black label except

 $v$. If unfortunately $u$ were the last node which will get covered,

 VF2 would check only in the last steps, whether $u$ can be matched to

 $v$.

 \newline

 However, had $u$ been the first matched node, u would have been

 matched immediately to v, so all the mappings would have been

 precluded in which node labels can not correspond.

 \end{example}

 \begin{example}

 Suppose there is no node label given, $G_{small}$ is a small graph and

 can not be mapped into $G_{large}$ and $u\in V_{small}$.

 \newline

 Let $G'_{small}:=(V_{small}\cup

 \{u'_{1},u'_{2},..,u'_{k}\},E_{small}\cup

 \{(u,u'_{1}),(u'_{1},u'_{2}),..,(u'_{k-1},u'_{k})\})$, that is,

 $G'_{small}$ is $G_{small}\cup \{ a\ k$ long path, which is disjoint

 from $G_{small}$ and one of its starting points is connected to $u\in

 V_{small}\}$.

 \newline

 Is there a subgraph of $G_{large}$, which is isomorph with

 $G'_{small}$?

 \newline

 If unfortunately the nodes of the path were the first $k$ nodes in the

 matching order, the algorithm would iterate through all the possible k

 long paths in $G_{large}$, and it would recognize that no path can be

 extended to $G'_{small}$.

 \newline

 However, had it started by the matching of $G_{small}$, it would not

 have matched any nodes of the path.

 \end{example}

 These examples may look artificial, but the same problems also appear

 in real-world instances, even though in a less obvious way.

 \subsection{Total ordering}

 Instead of the total ordering relation, the matching order will be

 searched directly.

 \begin{notation}

 Let \textbf{F$_\mathcal{M}$(l)}$:=|\{v\in V_{large} :

 l=lab(v)\}|-|\{u\in V_{small}\backslash \mathcal{M} : l=lab(u)\}|$ ,

 where $l$ is a label and $\mathcal{M}\subseteq V_{small}$.

 \end{notation}

 \begin{definition}Let $\mathbf{arg\ max}_{f}(S) :=\{u : u\in S \wedge f(u)=max_{v\in S}\{f(v)\}\}$ and $\mathbf{arg\ min}_{f}(S) := arg\ max_{-f}(S)$, where $S$ is a finite set and $f:S\longrightarrow \mathbb{R}$.

 \end{definition}

 \begin{algorithm}

 \algtext*{EndIf}

 \algtext*{EndProcedure}

 \algtext*{EndWhile}

 \algtext*{EndFor}

 \caption{\hspace{0.5cm}$The\ method\ of\ VF2++\ for\ determining\ the\ node\ order$}\label{alg:VF2PPPseu}

 \begin{algorithmic}[1]

 \Procedure{VF2++order}{} \State $\mathcal{M}$ := $\emptyset$

 \Comment{matching order} \While{$V_{small}\backslash \mathcal{M}

   \neq\emptyset$} \State $r\in$ arg max$_{deg}$ (arg

 min$_{F_\mathcal{M}\circ lab}(V_{small}\backslash

 \mathcal{M})$)\label{alg:findMin} \State Compute $T$, a BFS tree with

 root node $r$.  \For{$d=0,1,...,depth(T)$} \State $V_d$:=nodes of the

 $d$-th level \State Process $V_d$ \Comment{See Algorithm

   \ref{alg:VF2PPProcess1}} \EndFor

 \EndWhile \EndProcedure

 \end{algorithmic}

 \end{algorithm}

 \begin{algorithm}

 \algtext*{EndIf}

 \algtext*{EndProcedure}%ne nyomtasson ..

 \algtext*{EndWhile}

 \caption{\hspace{.5cm}$The\ method\ for\ processing\ a\ level\ of\ the\ BFS\ tree$}\label{alg:VF2PPProcess1}

 \begin{algorithmic}[1]

 \Procedure{VF2++ProcessLevel1}{$V_{d}$} \While{$V_d\neq\emptyset$}

 \State $m\in$ arg min$_{F_\mathcal{M}\circ\ lab}($ arg max$_{deg}($arg

 max$_{Conn_{\mathcal{M}}}(V_{d})))$ \State $V_d:=V_d\backslash m$

 \State Append node $m$ to the end of $\mathcal{M}$ \State Refresh

 $F_\mathcal{M}$ \EndWhile \EndProcedure

 \end{algorithmic}

 \end{algorithm}

 Algorithm~\ref{alg:VF2PPPseu} is a high level description of the

 matching order procedure of VF2++. It computes a BFS tree for each

 component in ascending order of their rarest $lab$ and largest $deg$,

 whose root vertex is the component's minimal

 node. Algorithm~\ref{alg:VF2PPProcess1} is a method to process a level of the BFS tree, which appends the nodes of the current level in descending

 lexicographic order by $(Conn_{\mathcal{M}},deg,-F_\mathcal{M})$ separately

 to $\mathcal{M}$, and refreshes $F_\mathcal{M}$ immediately.

 Claim~\ref{claim:MOclaim} shows that Algorithm~\ref{alg:VF2PPPseu}

 provides a matching order.

 \subsection{Cutting rules}

 \label{VF2PPCuttingRules}

 This section presents the cutting rules of VF2++, which are improved

 by using extra information coming from the node labels.

 \begin{notation}

 Let $\mathbf{\Gamma_{small}^{l}(u)}:=\{\tilde{u} : lab(\tilde{u})=l

 \wedge \tilde{u}\in \Gamma_{small} (u)\}$ and

 $\mathbf{\Gamma_{large}^{l}(v)}:=\{\tilde{v} : lab(\tilde{v})=l \wedge

 \tilde{v}\in \Gamma_{large} (v)\}$, where $u\in V_{small}$, $v\in

 V_{large}$ and $l$ is a label.

 \end{notation}

 \subsubsection{Induced subgraph isomorphism}

 \begin{claim}

 \[LabCut_{IND}((u,v),M(s))\!:=\!\!\!\!\!\bigvee_{l\ is\ label}\!\!\!\!\!\!\!|\Gamma_{large}^{l} (v) \cap T_{large}(s)|\!<\!|\Gamma_{small}^{l}(u)\cap T_{small}(s)|\ \vee\]\[\bigvee_{l\ is\ label} \newline |\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| < |\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|\] is a cutting function by IND.

 \end{claim}

 \subsubsection{Graph isomorphism}

 \begin{claim}

 \[LabCut_{ISO}((u,v),M(s))\!:=\!\!\!\!\!\bigvee_{l\ is\ label}\!\!\!\!\!\!\!|\Gamma_{large}^{l} (v) \cap T_{large}(s)|\!\neq\!|\Gamma_{small}^{l}(u)\cap T_{small}(s)|\  \vee\]\[\bigvee_{l\ is\ label} \newline |\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| \neq |\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|\] is a cutting function by ISO.

 \end{claim}

 \subsubsection{Subgraph isomorphism}

 \begin{claim}

 \[LabCut_{SUB}((u,v),M(s))\!:=\!\!\!\!\!\bigvee_{l\ is\ label}\!\!\!\!\!\!\!|\Gamma_{large}^{l} (v) \cap T_{large}(s)|\!<\!|\Gamma_{small}^{l}(u)\cap T_{small}(s)|\] is a cutting function by SUB.

 \end{claim}

 \subsection{Implementation details}

 This section provides a detailed summary of an efficient

 implementation of VF2++.

 \subsubsection{Storing a mapping}

 After fixing an arbitrary node order ($u_0, u_1, ..,

 u_{|G_{small}|-1}$) of $G_{small}$, an array $M$ is usable to store

 the current mapping in the following way.

 \[

  M[i] =

   \begin{cases} 

    v & if\ (u_i,v)\ is\ in\ the\ mapping\\ INVALID &

    if\ no\ node\ has\ been\ mapped\ to\ u_i.

   \end{cases}

 \]

 Where $i\in\{0,1, ..,|G_{small}|-1\}$, $v\in V_{large}$ and $INVALID$

 means "no node".

 \subsubsection{Avoiding the recurrence}

 The recursion of Algorithm~\ref{alg:VF2Pseu} can be realized

 as a \textit{while loop}, which has a loop counter $depth$ denoting the

 all-time depth of the recursion. Fixing a matching order, let $M$

 denote the array storing the all-time mapping. Based on Claim~\ref{claim:claimCoverFromLeft},

 $M$ is $INVALID$ from index $depth$+1 and not $INVALID$ before

 $depth$. $M[depth]$ changes

 while the state is being processed, but the property is held before

 both stepping back to a predecessor state and exploring a successor

 state.

 The necessary part of the candidate set is easily maintainable or

 computable by following

 Section~\ref{candidateComputingVF2}. A much faster method

 has been designed for biological- and sparse graphs, see the next

 section for details.

 \subsubsection{Calculating the candidates for a node}

 Being aware of Claim~\ref{claim:claimCoverFromLeft}, the

 task is not to maintain the candidate set, but to generate the

 candidate nodes in $G_{large}$ for a given node $u\in V_{small}$.  In

 case of an expanding problem type and $M$ mapping, if a node $v\in

 V_{large}$ is a potential pair of $u\in V_{small}$, then $\forall

 u'\in V_{small} : (u,u')\in

 E_{small}\ and\ u'\ is\ covered\ by\ M\ \Rightarrow (v,Pair(M,u'))\in

 E_{large}$. That is, each covered neighbour of $u$ has to be mapped to

 a covered neighbour of $v$.

 Having said that, an algorithm running in $\Theta(deg)$ time is

 describable if there exists a covered node in the component containing

 $u$, and a linear one other wise.

 \subsubsection{Determining the node order}

 This section describes how the node order preprocessing method of

 VF2++ can efficiently be implemented.

 For using lookup tables, the node labels are associated with the

 numbers $\{0,1,..,|K|-1\}$, where $K$ is the set of the labels. It

 enables $F_\mathcal{M}$ to be stored in an array. At first, the node order

 $\mathcal{M}=\emptyset$, so $F_\mathcal{M}[i]$ is the number of nodes

 in $V_{small}$ having label i, which is easy to compute in

 $\Theta(|V_{small}|)$ steps.

 Representing $\mathcal{M}\subseteq V_{small}$ as an array of

 size $|V_{small}|$, both the computation of the BFS tree, and processing its levels by Algorithm~\ref{alg:VF2PPProcess1} can be done inplace by swapping nodes.

 \subsubsection{Cutting rules}

 In Section~\ref{VF2PPCuttingRules}, the cutting rules were

 described using the sets $T_{small}$, $T_{large}$, $\tilde T_{small}$

 and $\tilde T_{large}$, which are dependent on the all-time mapping

 (i.e. on the all-time state). The aim is to check the labeled cutting

 rules of VF2++ in $\Theta(deg)$ time.

 Firstly, suppose that these four sets are given in such a way, that

 checking whether a node is in a certain set takes constant time,

 e.g. they are given by their 0-1 characteristic vectors. Let $L$ be an

 initially zero integer lookup table of size $|K|$. After incrementing

 $L[lab(u')]$ for all $u'\in \Gamma_{small}(u) \cap T_{small}(s)$ and

 decrementing $L[lab(v')]$ for all $v'\in\Gamma_{large} (v) \cap

 T_{large}(s)$, the first part of the cutting rules is checkable in

 $\Theta(deg)$ time by considering the proper signs of $L$. Setting $L$

 to zero takes $\Theta(deg)$ time again, which makes it possible to use

 the same table through the whole algorithm. The second part of the

 cutting rules can be verified using the same method with $\tilde

 T_{small}$ and $\tilde T_{large}$ instead of $T_{small}$ and

 $T_{large}$. Thus, the overall complexity is $\Theta(deg)$.

 An other integer lookup table storing the number of covered neighbours

 of each node in $G_{large}$ gives all the information about the sets

 $T_{large}$ and $\tilde T_{large}$, which is maintainable in

 $\Theta(deg)$ time when a pair is added or substracted by incrementing

 or decrementing the proper indices. A further improvement is that the

 values of $L[lab(u')]$ in case of checking $u$ is dependent only on

 $u$, i.e. on the size of the mapping, so for each $u\in V_{small}$ an

 array of pairs (label, number of such labels) can be stored to skip

 the maintaining operations. Note that these arrays are at most of size

 $deg$. Skipping this trick, the number of covered neighbours has to be

 stored for each node of $G_{small}$ as well to get the sets

 $T_{small}$ and $\tilde T_{small}$.

 Using similar tricks, the consistency function can be evaluated in

 $\Theta(deg)$ steps, as well.

 \section{The VF2 Plus Algorithm}

 The VF2 Plus algorithm is a recently improved version of VF2. It was

 compared with the state of the art algorithms in \cite{VF2Plus} and

 has proven itself to be competitive with RI, the best algorithm on

 biological graphs.  \\ A short summary of VF2 Plus follows, which uses

 the notation and the conventions of the original paper.

 \subsection{Ordering procedure}

 VF2 Plus uses a sorting procedure that prefers nodes in $V_{small}$

 with the lowest probability to find a pair in $V_{small}$ and the

 highest number of connections with the nodes already sorted by the

 algorithm.

 \begin{definition}

 $(u,v)$ is a \textbf{feasible pair}, if $lab(u)=lab(v)$ and

   $deg(u)\leq deg(v)$, where $u\in{V_{small}}$ and $ v\in{V_{large}}$.

 \end{definition}

 $P_{lab}(L):=$ a priori probability to find a node with label $L$ in

 $V_{large}$

 \newline

 $P_{deg}(d):=$ a priori probability to find a node with degree $d$ in

 $V_{large}$

 \newline

 $P(u):=P_{lab}(L)*\bigcup_{d'>d}P_{deg}(d')$\\ $M$ is the set of

 already sorted nodes, $T$ is the set of nodes candidate to be

 selected, and $degreeM$ of a node is the number of its neighbours in

 $M$.

 \begin{algorithm}

 \algtext*{EndIf}%ne nyomtasson end if-et \algtext*{EndFor}%ne

 nyomtasson ..  \algtext*{EndProcedure}%ne nyomtasson ..

 \algtext*{EndWhile}

 \caption{}\label{alg:VF2PlusPseu}

 \begin{algorithmic}[1]

 \Procedure{VF2 Plus order}{} \State Select the node with the lowest

 $P$.  \If {more nodes share the same $P$} \State select the one with

 maximum degree \EndIf \If {more nodes share the same $P$ and have the

   max degree} \State select the first \EndIf \State Put the selected

 node in the set $M$. \label{alg:putIn} \State Put all its unsorted

 neighbours in the set $T$.  \If {$M\neq V_{small}$} \State From set

 $T$ select the node with maximum $degreeM$.  \If {more nodes have

   maximum $degreeM$} \State Select the one with the lowest $P$ \EndIf

 \If {more nodes have maximum $degreeM$ and $P$} \State Select the

 first.  \EndIf \State \textbf{goto \ref{alg:putIn}.}  \EndIf

 \EndProcedure

 \end{algorithmic}

 \end{algorithm}

 Using these notations, Algorithm~\ref{alg:VF2PlusPseu}

 provides the description of the sorting procedure.

 Note that $P(u)$ is not the exact probability of finding a consistent

 pair for $u$ by choosing a node of $V_{large}$ randomly, since

 $P_{lab}$ and $P_{deg}$ are not independent, though calculating the

 real probability would take quadratic time, which may be reduced by

 using fittingly lookup tables.

 \section{Experimental results}

 This section compares the performance of VF2++ and VF2 Plus. Both

 algorithms have run faster with orders of magnitude than VF2, thus its

 inclusion was not reasonable.

 \subsection{Biological graphs}

 The tests have been executed on a recent biological dataset created

 for the International Contest on Pattern Search in Biological

 Databases\cite{Content}, which has been constructed of molecule,

 protein and contact map graphs extracted from the Protein Data

 Bank\cite{ProteinDataBank}.

 The molecule dataset contains small graphs with less than 100 nodes

 and an average degree of less than 3. The protein dataset contains

 graphs having 500-10 000 nodes and an average degree of 4, while the

 contact map dataset contains graphs with 150-800 nodes and an average

 degree of 20.  \\

 In the following, the induced subgraph isomorphism and the graph

 isomorphism will be examined.

 This dataset provides graph pairs, between which all the induced subgraph isomorphisms have to be found. For run time results, please see Figure~\ref{fig:bioIND}.

 In an other experiment, the nodes of each graph in the database had been

 shuffled, and an isomorphism between the shuffled and the original

 graph was searched. The solution times are shown on Figure~\ref{fig:bioISO}.

 \begin{figure}[H]

 \vspace*{-2cm}

 \hspace*{-1.5cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{figure}[H]

 \begin{tikzpicture}[trim axis left, trim axis right]

 \begin{axis}[title=Molecules ISO,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \thinspace}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {Orig/moleculesIso.txt}; \addplot[mark=triangle*,mark

   size=1.8pt,color=red] table {VF2PPLabel/moleculesIso.txt};

 \end{axis}

 \end{tikzpicture}

 \caption{In the case of molecules, there is not such a significant

   difference, but VF2++ seems to be faster as the number of nodes

   increases.}\label{fig:ISOMolecule}

 \end{figure}

 \end{subfigure}

 \hspace*{1.5cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{figure}[H]

 \begin{tikzpicture}[trim axis left, trim axis right]

 \begin{axis}[title=Contact maps ISO,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \thinspace}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {Orig/contactMapsIso.txt}; \addplot[mark=triangle*,mark

   size=1.8pt,color=red] table {VF2PPLabel/contactMapsIso.txt};

 \end{axis}

 \end{tikzpicture}

 \caption{The results are closer to each other on contact maps, but

   VF2++ still performs consistently better.}\label{fig:ISOContact}

 \end{figure}

 \end{subfigure}

 \begin{center}

 \vspace*{-0.5cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{figure}[H]

 \begin{tikzpicture}[trim axis left, trim axis right]

 \begin{axis}[title=Proteins ISO,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \thinspace}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {Orig/proteinsIso.txt}; \addplot[mark=triangle*,mark

   size=1.8pt,color=red] table {VF2PPLabel/proteinsIso.txt};

 \end{axis}

 \end{tikzpicture}

 \caption{On protein graphs, VF2 Plus has a super linear time

   complexity, while VF2++ runs in near constant time. The difference

   is about two order of magnitude on large graphs.}\label{fig:ISOProt}

 \end{figure}

 \end{subfigure}

 \end{center}

 \vspace*{-0.6cm}

 \caption{\normalsize{Graph isomomorphism on biological graphs}}\label{fig:bioISO}

 \end{figure}

 \begin{figure}[H]

 \vspace*{-2cm}

 \hspace*{-1.5cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{figure}[H]

 \begin{tikzpicture}[trim axis left, trim axis right]

 \begin{axis}[title=Molecules IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \thinspace}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {Orig/Molecules.32.txt}; \addplot[mark=triangle*,mark

   size=1.8pt,color=red] table {VF2PPLabel/Molecules.32.txt};

 \end{axis}

 \end{tikzpicture}

 \caption{In the case of molecules, the algorithms have

   similar behaviour, but VF2++ is almost two times faster even on such

   small graphs.} \label{fig:INDMolecule}

 \end{figure}

 \end{subfigure}

 \hspace*{1.5cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{figure}[H]

 \begin{tikzpicture}[trim axis left, trim axis right]

 \begin{axis}[title=Contact maps IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \thinspace}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {Orig/ContactMaps.128.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {VF2PPLabel/ContactMaps.128.txt};

 \end{axis}

 \end{tikzpicture}

 \caption{On contact maps, VF2++ runs in near constant time, while VF2

   Plus has a near linear behaviour.} \label{fig:INDContact}

 \end{figure}

 \end{subfigure}

 \begin{center}

 \vspace*{-0.5cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{figure}[H]

 \begin{tikzpicture}[trim axis left, trim axis right]

   \begin{axis}[title=Proteins IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid

   =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

     west},scaled x ticks = false,x tick label style={/pgf/number

     format/1000 sep = \thinspace}] %\addplot+[only marks] table

     {proteinsOrig.txt}; \addplot[mark=*,mark size=1.2pt,color=blue]

     table {Orig/Proteins.256.txt}; \addplot[mark=triangle*,mark

       size=1.8pt,color=red] table {VF2PPLabel/Proteins.256.txt};

   \end{axis}

   \end{tikzpicture}

 \caption{Both the algorithms have linear behaviour on protein

   graphs. VF2++ is more than 10 times faster than VF2

   Plus.} \label{fig:INDProt}

 \end{figure}

 \end{subfigure}

 \end{center}

 \vspace*{-0.5cm}

 \caption{\normalsize{Graph isomomorphism on biological graphs}}\label{fig:bioIND}

 \end{figure}

 \subsection{Random graphs}

 This section compares VF2++ with VF2 Plus on random graphs of a large

 size. The node labels are uniformly distributed.  Let $\delta$ denote

 the average degree.  For the parameters of problems solved in the

 experiments, please see the top of each chart.

 \subsubsection{Graph isomorphism}

 To evaluate the efficiency of the algorithms in the case of graph

 isomorphism, connected graphs of less than 20 000 nodes have been

 considered. Generating a random graph and shuffling its nodes, an

 isomorphism had to be found. Figure \ref{fig:randISO} shows the runtime results

 on graph sets of various density.

 \begin{figure}

 \vspace*{-1.5cm}

 \hspace*{-1.5cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{center}

 \begin{tikzpicture}

 \begin{axis}[title={Random ISO, $\delta = 5$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/iso/vf2pIso5_1.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/iso/vf2ppIso5_1.txt};

 \end{axis}

 \end{tikzpicture}

 \end{center}

 \end{subfigure}

 %\hspace{1cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{center}

 \begin{tikzpicture}

 \begin{axis}[title={Random ISO, $\delta = 10$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/iso/vf2pIso10_1.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/iso/vf2ppIso10_1.txt};

 \end{axis}

 \end{tikzpicture}

 \end{center}

 \end{subfigure}

 %%\hspace{1cm}

 \hspace*{-1.5cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{center}

 \begin{tikzpicture}

 \begin{axis}[title={Random ISO, $\delta = 15$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/iso/vf2pIso15_1.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/iso/vf2ppIso15_1.txt};

 \end{axis}

 \end{tikzpicture}

 \end{center}

      \end{subfigure}

      \begin{subfigure}[b]{0.55\textwidth}

 \begin{center}

 \begin{tikzpicture}

 \begin{axis}[title={Random ISO, $\delta = 35$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/iso/vf2pIso35_1.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/iso/vf2ppIso35_1.txt};

 \end{axis}

 \end{tikzpicture}

 \end{center}

 \end{subfigure}

 \begin{subfigure}[b]{0.55\textwidth}

 \hspace*{-1.5cm}

 \begin{tikzpicture}

 \begin{axis}[title={Random ISO, $\delta = 45$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/iso/vf2pIso45_1.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/iso/vf2ppIso45_1.txt};

 \end{axis}

 \end{tikzpicture}

 \end{subfigure}

 \hspace*{-1.5cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{tikzpicture}

 \begin{axis}[title={Random ISO, $\delta = 100$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \thinspace}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/iso/vf2pIso100_1.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/iso/vf2ppIso100_1.txt};

 \end{axis}

 \end{tikzpicture}

 \end{subfigure}

 \vspace*{-0.8cm}

 \caption{IND on graphs having an average degree of

   5.}\label{fig:randISO}

 \end{figure}

 Considering the graph isomorphism problem, VF2++ consistently

 outperforms its rival especially on sparse graphs. The reason for the

 slightly super linear behaviour of VF2++ on denser graphs is the

 larger number of nodes in the BFS tree constructed in

 Algorithm~\ref{alg:VF2PPPseu}.

 \subsubsection{Induced subgraph isomorphism}

 This section provides a comparison of VF2++ and VF2 Plus in the case

 of induced subgraph isomorphism. In addition to the size of the large

 graph, that of the small graph dramatically influences the hardness of

 a given problem too, so the overall picture is provided by examining

 small graphs of various size.

 For each chart, a number $0<\rho< 1$ has been fixed and the following

 has been executed 150 times. Generating a large graph $G_{large}$,

 choose 10 of its induced subgraphs having $\rho\ |V_{large}|$ nodes,

 and for all the 10 subgraphs find a mapping by using both the graph

 matching algorithms.  The $\delta = 5, 10, 35$ and $\rho = 0.05, 0.1,

 0.3, 0.6, 0.8, 0.95$ cases have been examined, see

 Figure~\ref{fig:randIND5}, \ref{fig:randIND10} and

 \ref{fig:randIND35}.

 \begin{figure}

 \vspace*{-1.5cm}

 \hspace*{-1.5cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{center}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.05$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd5_0.05.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd5_0.05.txt};

 \end{axis}

 \end{tikzpicture}

 \end{center}

      \end{subfigure}

      \begin{subfigure}[b]{0.55\textwidth}

 \begin{center}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.1$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd5_0.1.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd5_0.1.txt};

 \end{axis}

 \end{tikzpicture}

 \end{center}

 \end{subfigure}

 \hspace*{-1.5cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{center}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.3$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd5_0.3.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd5_0.3.txt};

 \end{axis}

 \end{tikzpicture}

 \end{center}

      \end{subfigure}

      \begin{subfigure}[b]{0.55\textwidth}

 \begin{center}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.6$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd5_0.6.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd5_0.6.txt};

 \end{axis}

 \end{tikzpicture}

 \end{center}

 \end{subfigure}

 \begin{subfigure}[b]{0.55\textwidth}

 \hspace*{-1.5cm}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd5_0.8.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd5_0.8.txt};

 \end{axis}

 \end{tikzpicture}

      \end{subfigure}

      \hspace*{-1.5cm}

      \begin{subfigure}[b]{0.55\textwidth}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.95$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \thinspace}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd5_0.95.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd5_0.95.txt};

 \end{axis}

 \end{tikzpicture}

 \end{subfigure}

 \vspace*{-0.8cm}

 \caption{IND on graphs having an average degree of

   5.}\label{fig:randIND5}

 \end{figure}

 \begin{figure}[H]

 \vspace*{-1.5cm}

 \hspace*{-1.5cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{center}

 \hspace*{-0.5cm}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.05$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd10_0.05.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd10_0.05.txt};

 \end{axis}

 \end{tikzpicture}

 \end{center}

      \end{subfigure}

      \begin{subfigure}[b]{0.55\textwidth}

 \begin{center}

      \hspace*{-0.5cm}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.1$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd10_0.1.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd10_0.1.txt};

 \end{axis}

 \end{tikzpicture}

 \end{center}

 \end{subfigure}

 \hspace*{-1.5cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{center}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.3$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd10_0.3.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd10_0.3.txt};

 \end{axis}

 \end{tikzpicture}

 \end{center}

      \end{subfigure}

      \begin{subfigure}[b]{0.55\textwidth}

 \begin{center}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.6$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd10_0.6.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd10_0.6.txt};

 \end{axis}

 \end{tikzpicture}

 \end{center}

 \end{subfigure}

 \hspace*{-1.5cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd10_0.8.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd10_0.8.txt};

 \end{axis}

 \end{tikzpicture}

      \end{subfigure}

      \begin{subfigure}[b]{0.55\textwidth}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.95$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \thinspace}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd10_0.95.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd10_0.95.txt};

 \end{axis}

 \end{tikzpicture}

 \end{subfigure}

 \vspace*{-0.8cm}

 \caption{IND on graphs having an average degree of

   10.}\label{fig:randIND10}

 \end{figure}

 \begin{figure}[H]

 \vspace*{-1.5cm}

 \hspace*{-1.5cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{center}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.05$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd35_0.05.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd35_0.05.txt};

 \end{axis}

 \end{tikzpicture}

 \end{center}

      \end{subfigure}

      \begin{subfigure}[b]{0.55\textwidth}

 \begin{center}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.1$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd35_0.1.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd35_0.1.txt};

 \end{axis}

 \end{tikzpicture}

 \end{center}

 \end{subfigure}

 \hspace*{-1.5cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{center}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.3$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd35_0.3.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd35_0.3.txt};

 \end{axis}

 \end{tikzpicture}

 \end{center}

      \end{subfigure}

      \begin{subfigure}[b]{0.55\textwidth}

 \begin{center}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.6$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd35_0.6.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd35_0.6.txt};

 \end{axis}

 \end{tikzpicture}

 \end{center}

 \end{subfigure}

 \hspace*{-1.5cm}

 \begin{subfigure}[b]{0.55\textwidth}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \space}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd35_0.8.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd35_0.8.txt};

 \end{axis}

 \end{tikzpicture}

      \end{subfigure}

      \begin{subfigure}[b]{0.55\textwidth}

 \begin{tikzpicture}

 \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.95$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid

 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north

   west},scaled x ticks = false,x tick label style={/pgf/number

   format/1000 sep = \thinspace}]

 %\addplot+[only marks] table {proteinsOrig.txt};

 \addplot table {randGraph/ind/vf2pInd35_0.95.txt};

 \addplot[mark=triangle*,mark size=1.8pt,color=red] table

         {randGraph/ind/vf2ppInd35_0.95.txt};

 \end{axis}

 \end{tikzpicture}

 \end{subfigure}

 \vspace*{-0.8cm}

 \caption{IND on graphs having an average degree of

   35.}\label{fig:randIND35}

 \end{figure}

 Based on these experiments, VF2++ is faster than VF2 Plus and able to

 handle really large graphs in milliseconds. Note that when $IND$ was

 considered and the small graphs had proportionally few nodes ($\rho =

 0.05$, or $\rho = 0.1$), then VF2 Plus produced some inefficient node

 orders (e.g. see the $\delta=10$ case on

 Figure~\ref{fig:randIND10}). If these examples had been excluded, the

 charts would have seemed to be similar to the other ones.

 Unsurprisingly, as denser graphs are considered, both VF2++ and VF2

 Plus slow slightly down, but remain practically usable even on graphs

 having 10 000 nodes.

 \section{Conclusion}

 In this paper, after providing a short summary of the recent

 algorithms, a new graph matching algorithm based on VF2, called VF2++,

 has been presented and analyzed from a practical viewpoint.

 Recognizing the importance of the node order and determining an

 efficient one, VF2++ is able to match graphs of thousands of nodes in

 near practically linear time including preprocessing. In addition to

 the proper order, VF2++ uses more efficient consistency and cutting

 rules which are easy to compute and make the algorithm able to prune

 most of the unfruitful branches without going astray.

 In order to show the efficiency of the new method, it has been

 compared to VF2 Plus, which is the best concurrent algorithm based on

 \cite{VF2Plus}.

 The experiments show that VF2++ consistently outperforms VF2 Plus on

 biological graphs. It seems to be asymptotically faster on protein and

 on contact map graphs in the case of induced subgraph isomorphism,

 while in the case of graph isomorphism, it has definitely better

 asymptotic behaviour on protein graphs.

 Regarding random sparse graphs, not only has VF2++ proved itself to be

 faster than VF2 Plus, but it has a practically linear behaviour both

 in the case of induced subgraph- and graph isomorphism, as well.

 %% The Appendices part is started with the command \appendix;

 %% appendix sections are then done as normal sections

 %% \appendix

 %% \section{}

 %% \label{}

 %% If you have bibdatabase file and want bibtex to generate the

 %% bibitems, please use

 %%

 \bibliographystyle{elsarticle-num} \bibliography{bibliography}

 %% else use the following coding to input the bibitems directly in the

 %% TeX file.

 %% \begin{thebibliography}{00}

 %% %% \bibitem{label}

 %% %% Text of bibliographic item

 %% \bibitem{}

 %% \end{thebibliography}

 \end{document}

 \endinput

 %%

 %% End of file `elsarticle-template-num.tex'.