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.

 In the last decades, combinatorial structures, and especially graphs

 The expressiveness, the simplicity and the studiedness of graphs make them practical for modelling and appear constantly in several seemingly independent fields.

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

 Bioinformatics and chemistry are amongst the most relevant and most important fields.

 solution of several new and revised questions.  The expressiveness,

 the simplicity and the studiedness of graphs make them practical for

 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.

 modelling and appear constantly in several seemingly independent

 fields.  Bioinformatics and chemistry are amongst the most relevant

 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.

 and most important fields.

 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.

 Complex biological systems arise from the interaction and cooperation

 of plenty of molecular components. Getting acquainted with such

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

 systems at the molecular level has primary importance, since

 \\

 protein-protein interaction, DNA-protein interaction, metabolic

 interaction, transcription factor binding, neuronal networks, and

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

 hormone signaling networks can be understood only this way.

 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.

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

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

 The first practically usable approach was due to \textbf{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.

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

 where nodes are associated with aminoacids and the edges with hydrogen

 In a recent paper, \textbf{Ullmann}\cite{UllmannBit} presents an improved version of this algorithm based on a bit-vector solution for the binary Constraint Satisfaction Problem.

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

 represent some relationships among them.  The similarity and

 The \textbf{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.

 dissimilarity of objects corresponding to nodes are incorporated to

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

 The \textbf{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.

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

 networks basically requires finding specific subgraphs, which can not

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

 avoid the application of graph matching algorithms.

 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.

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

 variants of graph matching be briefly mentioned: pattern recognition

 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.

 and machine vision \cite{HorstBunkeApplications}, symbol recognition

 \cite{CordellaVentoSymbolRecognition}, face identification

 This thesis 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.

 \cite{JianzhuangYongFaceIdentification}.  \\

 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.\newline

 Subgraph and induced subgraph matching problems are known to be

 \newline

 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

 \textbf{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, \textbf{Ullmann}\cite{UllmannBit} presents an

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

 the binary Constraint Satisfaction Problem.

 The \textbf{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 \textbf{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.

 This section provides a detailed description of the problems to be solved.

 This section provides a detailed description of the problems to be

 solved.

 Throughout the paper $G_{small}=(V_{small}, E_{small})$ and $G_{large}=(V_{large}, E_{large})$ denote two undirected graphs.

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

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

 $G_{small}$ and $G_{large}$ are \textbf{isomorphic} if $\exists M: V_{small} \longrightarrow V_{large}$ bijection, for which the following is true:

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

 \begin{center}

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

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

   following is true:

 \begin{center}

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

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

 For the sake of simplicity in this paper subgraphs and induced subgraphs are defined in a more general way than usual:

 For the sake of simplicity in this paper subgraphs and induced

 subgraphs are defined in a more general way than usual:

 $G_{small}$ is a \textbf{subgraph} of $G_{large}$ if $\exists I: V_{small}\longrightarrow V_{large}$ injection, for which the following is true:

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

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

   following is true:

 $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:

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

 \begin{center}

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

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

   following is true:

 \begin{center}

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

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

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

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

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

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

 For example, the node labeled isomorphism is phrased by

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

 $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:

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

 \begin{center}

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

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

   bijection, for which the following is true:

  and $(\forall u\in{V_{small}} : lab(u)=lab(M(u)))$

 \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)))$

 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.

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

 function, and all the definitions can be extended with additional

 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.

 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.

 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 focus of this paper is on two extensively studied topics, the

 subgraph isomorphism and its variations. However, the following

 The \textbf{subgraph matching problem} is the following: is $G_{small}$ isomorphic to any subgraph of $G_{large}$ by a given node label?

 problems also appear in many applications.

 The \textbf{induced subgraph matching problem} asks the same about the existence of an induced subgraph.

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

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

 The \textbf{graph isomorphism problem} can be defined as induced subgraph matching problem where the sizes of the two graphs are equal.

 label?

 In addition to existence, it may be needed to show such a subgraph, or it may be necessary to list all of them.

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

 existence of an induced subgraph.

 It should be noted that some authors misleadingly refer to the term \emph{subgraph isomorphism problem} as an \emph{induced subgraph isomorphism problem}.

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

 The following sections give the descriptions of VF2, VF2++, VF2 Plus and a particular comparison.

 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.

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

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

 VF2 is able to handle all the variations mentioned in \textbf{Section \ref{sec:CommProb})}.

 is able to handle all the variations mentioned in \textbf{Section

 Although it can also handle directed graphs, for the sake of simplicity, only the undirected case will be discussed.

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

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

 discussed.

 \indent

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

 Assume $G_{small}$ is searched in $G_{large}$.

 definitions and notations will be used throughout the whole paper.

 The following definitions and notations will be used throughout the whole paper.

 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.

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

 That is, M uniquely associates some of the nodes in $V_{small}$ with some nodes of $V_{large}$ and vice versa.

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

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

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

 contains v.

 A mapping $M$ is $\mathbf{whole\ mapping}$, if $M$ covers all the nodes in $V_{small}$.

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

 nodes in $V_{small}$.

 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)\}$.

 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)\}$.

 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}$.

 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}$.

 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 

 The definitions of the isomorphism types can be rephrased on the

 \begin{center}

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

 $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}$.

 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}$.

 Throughout the paper, $\mathbf{PT}$ denotes a generic problem type which can be substituted by any problem type.

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

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

 For example the problem type of graph isomorphism problem is the following.

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

 A whole mapping $W$ is in $\mathbf{ISO}$, iff the bijection represented by $W$ satisfies \textbf{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}$.

 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 \textbf{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}$.

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

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

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

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

 the following generic definitions make it possible to handle other types as well.

 but the following generic definitions make it possible to handle other

 Although it may be challenging to find a proper consistency function and an efficient

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

 cutting function.

 consistency function and an efficient cutting function.

 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.

 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.

 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.

 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.

 $M$ is said to be \textbf{consistent mapping by} $\mathbf{PT}$, if $Cons_{PT}(M)$ is true. 

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

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

 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.

 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.

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

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

 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.

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

 Each state $s$ of the matching process can be associated with a mapping $M(s)$.

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

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

 \textbf{Algorithm~\ref{alg:VF2Pseu})} is a high level description of the VF2 matching algorithm.

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

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

 the VF2 matching algorithm.

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

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

 \algtext*{EndFor}%ne nyomtasson ..

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

 \algtext*{EndProcedure}%ne nyomtasson ..

 \Procedure{VF2}{State $s$, ProblemType $PT$}

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

   \If{$M(s$) covers $V_{small}$}

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

     \State Output($M(s)$)

   \Else

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

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

   \ForAll{$p\in{P(s)}$}

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

     \If{Cons$_{PT}$($p, M(s)$) $\wedge$ $\neg$Cut$_{PT}$($p, M(s)$)}

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

       \State Compute the nascent state $\tilde{s}$ by adding $p$ to $M(s)$

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

       \State \textbf{call} VF2($\tilde{s}$, $PT$)

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

     \EndIf

   \EndFor

   \EndIf

 \EndProcedure

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

 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 state $s$, the algorithm computes $P(s)$, the set of

 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.

 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.

 Through consistent mappings, only consistent whole mappings can be reached, and all of the whole mappings are reachable through consistent mappings.

 Through consistent mappings, only consistent whole mappings can be

 reached, and all of the whole mappings are reachable through

 consistent mappings.

 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.

 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.

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

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

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

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

 then no state can be reached more than ones and each state associated with a whole mapping remains reachable. 

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

 with a whole mapping remains reachable.

 Note that the cornerstone of the improvements to VF2 is a proper choice of a total ordering.

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

 choice of a total ordering.

 Suppose that $PT$ is an expanding problem type, see \textbf{Definition~\ref{expPT})}.

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

 \textbf{Definition~\ref{expPT})}.

 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)\}$

 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)\}$

 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

 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

    T_{small}(s)\times T_{large}(s)&\hspace{-0.15cm}\text{if } T_{small}(s)\!\neq\!\emptyset\!\wedge\!T_{large}(s)\!\neq \emptyset,\\

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

    (V_{small}\!\setminus\!M_{small}(s))\!\times\!(V_{large}\!\setminus\!M_{large}(s)) &\hspace{-0.15cm}otherwise.

    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.

 This section defines the consistency functions for the different problem types mentioned in \textbf{Section \ref{sec:CommProb})}.

 This section defines the consistency functions for the different

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

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

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

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

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

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

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

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

 $s$ is a state of the matching procedure,

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

 $M(s)$ is consistent mapping by $PT$ and $lab(u)=lab(v)$.

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

 $Cons_{PT}(p,M(s))$ checks whether including pair $p$ into $M(s)$ leads to a consistent mapping by $PT$.

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

 $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

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

 The following formulation gives an efficient way of calculating $Cons_{IND}$.

 (\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}$.

 $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 

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

 (\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$.

   \ \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$.

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

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

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

 $IND$.

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

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

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

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

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

 The following formulation gives an efficient way of calculating $Cons_{SUB}$.

 The following formulation gives an efficient way of calculating

 $Cons_{SUB}$.

 $Cons_{SUB}((u,v),M(s)):=

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

 (\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$.

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

   consistency function by $SUB$.

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

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

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

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

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

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

 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.

 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.

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

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

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

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

 Note that there is a significant difference between induced and non-induced subgraph isomorphism:

 Note that there is a significant difference between induced and

 non-induced subgraph isomorphism:

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

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

   \node[rectangle,fill=black!15] at (4,6) {$G_{small}$};

   \node[rectangle,fill=black!15] at (4,6) {$G_{small}$}; \node (u4) at

   \node (u4) at (2.5,10)  {$u_4$};

   (2.5,10) {$u_4$}; \node (u3) at (5.5,10) {$u_3$}; \node (u1) at

   \node (u3) at (5.5,10) {$u_3$};

   (2.5,7) {$u_1$}; \node (u2) at (5.5,7) {$u_2$};

   \node (u1) at (2.5,7)  {$u_1$};

   \node (u2) at (5.5,7) {$u_2$};

   \node[fill=black!30] (v4) at (12,10)  {$v_4$};

   \node[fill=black!30] (v4) at (12,10) {$v_4$}; \node[fill=black!30]

   \node[fill=black!30] (v3) at (15,10) {$v_3$};

   (v3) at (15,10) {$v_3$}; \node[fill=black!30] (v1) at (12,7)

   \node[fill=black!30] (v1) at (12,7)  {$v_1$};

        {$v_1$}; \node[fill=black!30] (v2) at (15,7) {$v_2$};

   \node[fill=black!30] (v2) at (15,7) {$v_2$};

   \foreach \from/\to in {u1/u2,u2/u3,u3/u4,u4/u1}

   \foreach \from/\to in {u1/u2,u2/u3,u3/u4,u4/u1} \draw (\from) --

     \draw (\from) -- (\to);

   (\to); \foreach \from/\to in {v1/v2,v2/v3,v3/v4,v4/v1,v1/v3} \draw

   \foreach \from/\to in {v1/v2,v2/v3,v3/v4,v4/v1,v1/v3}

   (\from) -- (\to);

     \draw (\from) -- (\to);

 \caption{Graphs for the proof of \textbf{Claim \ref{claimSUB}}} \label{fig:proofSUB}

 \caption{Graphs for the proof of \textbf{Claim

     \ref{claimSUB}}} \label{fig:proofSUB}

 Let the two graphs of \textbf{Figure \ref{fig:proofSUB})} be the input graphs.

 Let the two graphs of \textbf{Figure \ref{fig:proofSUB})} be the input

 Suppose the total ordering relation is $u_1 \prec u_2 \prec u_3 \prec u_4$,$M(s)\!=\{(u_1,v_1)\}$, and VF2 tries to add $(u_2,v_2)\in P(s)$.\newline

 graphs.  Suppose the total ordering relation is $u_1 \prec u_2 \prec

 $Cons_{SUB}((u_2,v_2),M(s))=true$, so $M\cup \{(u_2,v_2)\}$ is consistent by $SUB$. The cutting function $Cut_{SUB}((u_2,v_2),M(s))$ is false, so it does not let cut the tree.\newline

 u_3 \prec u_4$,$M(s)\!=\{(u_1,v_1)\}$, and VF2 tries to add

 On the other hand $Cut_{SUB}'((u_2,v_2),M(s))$ is true, since\\$0=|\Gamma_{large}(v_2)\cap \tilde{T}_{large}(s)|<|\Gamma_{small}(u_2)\cap \tilde{T}_{small}(s)|=1$ is true, but still the tree can not be pruned, because otherwise the $\{(u_1,v_1)(u_2,v_2)(u_3,v_3)(u_4,v_4)\}$ mapping can not be found.

 $(u_2,v_2)\in P(s)$.\newline $Cons_{SUB}((u_2,v_2),M(s))=true$, so

 $M\cup \{(u_2,v_2)\}$ is consistent by $SUB$. The cutting function

 $Cut_{SUB}((u_2,v_2),M(s))$ is false, so it does not let cut the

 tree.\newline On the other hand $Cut_{SUB}'((u_2,v_2),M(s))$ is true,

 since\\$0=|\Gamma_{large}(v_2)\cap

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

 \tilde{T}_{small}(s)|=1$ is true, but still the tree can not be

 pruned, because otherwise the

 $\{(u_1,v_1)(u_2,v_2)(u_3,v_3)(u_4,v_4)\}$ mapping can not be found.

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

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

 choice turns out to dramatically influence the number of visited states. The goal is to determine an efficient one as quickly as possible.

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

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

 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.

 as possible.

 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.

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

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

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

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

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

 branches of the search space can be pruned immediately. Secondly,

 introducing more efficient --- nevertheless still easier to compute

 It should be noted that all the methods described in this section are extendable to handle directed graphs and edge labels as well.

 --- cutting rules reduces the chance of going astray even further.

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

 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.

 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.

 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.

 In order to make the search space a tree, the pairs in $\{(u,v)\in P(s) : \exists \hat{u} : \hat{u}\prec u\}$ are excluded from $P(s)$.

 In order to make the search space a tree, the pairs in $\{(u,v)\in

 P(s) : \exists \hat{u} : \hat{u}\prec u\}$ are excluded from $P(s)$.

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

 Let $\tilde{P}(s):=P(s)\backslash \{(u,v)\in P(s) : \exists \hat{u} :

 \hat{u}\prec u\}$

 The relation $\prec$ is a total ordering, so $\exists!\ \tilde{u} : \forall\ (u,v)\in \tilde{P}(s): u=\tilde u$. Since a pair form $\tilde{P}(s)$ is chosen for including into $M(s)$, it is obvious, that only $\tilde{u}$ can be covered in $V_{small}$. Actually, $\tilde{u}$ is the smallest element in $T_{small}(s)$ (or in $V_{small}\backslash M_{small}(s)$, if $T_{small}(s)$ were empty), and $T_{small}(s)$ depends only on the covered nodes of $G_{small}$. 

 The relation $\prec$ is a total ordering, so $\exists!\ \tilde{u} :

 \forall\ (u,v)\in \tilde{P}(s): u=\tilde u$. Since a pair form

 $\tilde{P}(s)$ is chosen for including into $M(s)$, it is obvious,

 that only $\tilde{u}$ can be covered in $V_{small}$. Actually,

 $\tilde{u}$ is the smallest element in $T_{small}(s)$ (or in

 $V_{small}\backslash M_{small}(s)$, if $T_{small}(s)$ were empty), and

 $T_{small}(s)$ depends only on the covered nodes of $G_{small}$.

 Simple induction on $d$ shows that the set of covered nodes of $G_{small}$ is unique, if $d$ is given, so $\tilde{u}$ is unique if $d$ is given.

 Simple induction on $d$ shows that the set of covered nodes of

 $G_{small}$ is unique, if $d$ is given, so $\tilde{u}$ is unique if

 $d$ is given.

 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}|\}$.

 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}|\}$.

 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.

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

 \\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

 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

 Suppose a matching order is given. It has to be shown that the node sequence has a structure described above.\\

 Suppose a matching order is given. It has to be shown that the node

 Let $G'_{small}=(V'_{small},E'_{small})$ be an arbitrary component and $i$ an arbitrary index. 

 sequence has a structure described above.\\ Let

 $G'_{small}=(V'_{small},E'_{small})$ be an arbitrary component and $i$

 an arbitrary index.

 $(\exists j : j<i\wedge u_{\sigma(j)},u_{\sigma(i)}\in V'_{small})\Rightarrow u_{\sigma(i)}$ is not the first covered node in $G_{small}\ \Rightarrow u_{\sigma(i)}$ is connected to a covered node $u_{\sigma(k)}$ where $k<i$, since $u_{\sigma(i)}\in T_{small}(s)$ for some $s$ and $T_{small}(s)\subseteq{V'_{small}}$ contains only nodes connected to at least one covered node. It's easy to see, that $\forall l: k\leq l\leq i \Rightarrow u_{l}\in V'_{small}$, since $T_{small}(s)$ contains only nodes connected to some covered ones, while it is not empty, but if it were empty, then $u_{\sigma(k)}$ and $u_{\sigma(i)}$ were not in the same component.

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

 V'_{small})\Rightarrow u_{\sigma(i)}$ is not the first covered node in

 Now, let us show that if a node sequence has the special structure described above, it has to be matching order.\\ $(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$ is a total ordering, which determines the matching order $(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$.

 $G_{small}\ \Rightarrow u_{\sigma(i)}$ is connected to a covered node

 $u_{\sigma(k)}$ where $k<i$, since $u_{\sigma(i)}\in T_{small}(s)$ for

 some $s$ and $T_{small}(s)\subseteq{V'_{small}}$ contains only nodes

 connected to at least one covered node. It's easy to see, that

 $\forall l: k\leq l\leq i \Rightarrow u_{l}\in V'_{small}$, since

 $T_{small}(s)$ contains only nodes connected to some covered ones,

 while it is not empty, but if it were empty, then $u_{\sigma(k)}$ and

 $u_{\sigma(i)}$ were not in the same component.

 Now, let us show that if a node sequence has the special structure

 described above, it has to be matching

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

 a total ordering, which determines the matching order

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

 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.

 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.

 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.

 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.

 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}$.

 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}$.

 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.

 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

 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.

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

 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.

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

 The tertiary ordering prefers nodes having the rarest uncovered labels.

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

 are given.

 Note that the secondary ordering is the same as the ordering by $deg$, which is a static data in front of the above used.

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

 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.

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

 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.

 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.

 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}$.

 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}$.

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

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

 \{u\})$

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

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

 \{v\})$

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

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

 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.

 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.

 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}$.

 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}$.

 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}\}$.

 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}\}$.

 Is there a subgraph of $G_{large}$, which is isomorph with $G'_{small}$?

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

 $G'_{small}$?

 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}$.

 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}$.

 However, had it started by the matching of $G_{small}$, it would not have matched any nodes of the path.

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

 have matched any nodes of the path.

 These examples may look artificial, but the same problems also appear in real-world examples, even though in a less obvious way.

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

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

 Instead of the total ordering relation, the matching order will be searched directly.

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

 searched directly.

 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}$.

 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}$.

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

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

 \algtext*{EndFor}%ne nyomtasson ..

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

 \algtext*{EndProcedure}%ne nyomtasson ..

 \Procedure{VF2++order}{}

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

   \State $\mathcal{M}$ := $\emptyset$ \Comment{matching order}

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

   \While{$V_{small}\backslash \mathcal{M} \neq\emptyset$}

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

   \State $r\in$ arg max$_{deg}$ (arg min$_{F_\mathcal{M}\circ lab}(V_{small}\backslash \mathcal{M})$)\label{alg:findMin}

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

   \State Compute $T$, a BFS tree with root node $r$.

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

   \For{$d=0,1,...,depth(T)$}

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

   \State $V_d$:=nodes of the $d$-th level

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

   \State Process $V_d$ \Comment{See Algorithm \ref{alg:VF2PPProcess1}) and \ref{alg:VF2PPProcess2})}

   \ref{alg:VF2PPProcess1}) and \ref{alg:VF2PPProcess2})} \EndFor

   \EndFor

 \EndWhile \EndProcedure

   \EndWhile

 \EndProcedure

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

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

 \algtext*{EndFor}%ne nyomtasson ..

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

 \algtext*{EndProcedure}%ne nyomtasson ..

 \Procedure{VF2++ProcessLevel1}{$V_{d}$}

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

   \While{$V_d\neq\emptyset$}

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

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

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

   \State $V_d:=V_d\backslash m$

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

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

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

   \State Refresh $F_\mathcal{M}$

   \EndWhile

 \EndProcedure

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

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

 \algtext*{EndFor}%ne nyomtasson ..

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

 \algtext*{EndProcedure}%ne nyomtasson ..

 \Procedure{VF2++ProcessLevel2}{$V_{d}$}

 \Procedure{VF2++ProcessLevel2}{$V_{d}$} \State Sort $V_d$ in

   \State Sort $V_d$ in descending lex. order by $(Conn_{\mathcal{M}},deg,-F_\mathcal{M})$

 descending lex. order by $(Conn_{\mathcal{M}},deg,-F_\mathcal{M})$

   \State Append the sorted $V_d$ to the end of $\mathcal{M}$

 \State Append the sorted $V_d$ to the end of $\mathcal{M}$ \State

   \State Refresh $F_\mathcal{M}$

 Refresh $F_\mathcal{M}$ \EndProcedure

 \EndProcedure

 \textbf{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. \textbf{Algorithm \ref{alg:VF2PPProcess1})} and \textbf{\ref{alg:VF2PPProcess2})} are two different methods to process a level of the BFS tree.

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

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

 After sorting the nodes of the current level in descending lexicographic order by $(Conn_{\mathcal{M}},deg,-F_\mathcal{M})$, \textbf{Algorithm \ref{alg:VF2PPProcess2})} appends them simultaneously to the matching order $\mathcal{M}$ and refreshes $F_\mathcal{M}$ just once, whereas \textbf{Algorithm \ref{alg:VF2PPProcess1})} appends the nodes separately to $\mathcal{M}$ and refreshes $F_\mathcal{M}$ immediately, so it provides up-to-date label information and may result in a more efficient matching order.

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

 whose root vertex is the component's minimal node. \textbf{Algorithm

 \textbf{Claim~\ref{claim:MOclaim})} shows that \textbf{Algorithm \ref{alg:VF2PPPseu})} provides a matching order.

   \ref{alg:VF2PPProcess1})} and \textbf{\ref{alg:VF2PPProcess2})} are

 two different methods to process a level of the BFS tree.

 After sorting the nodes of the current level in descending

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

 \textbf{Algorithm \ref{alg:VF2PPProcess2})} appends them

 simultaneously to the matching order $\mathcal{M}$ and refreshes

 $F_\mathcal{M}$ just once, whereas \textbf{Algorithm

   \ref{alg:VF2PPProcess1})} appends the nodes separately to

 $\mathcal{M}$ and refreshes $F_\mathcal{M}$ immediately, so it

 provides up-to-date label information and may result in a more

 efficient matching order.

 \textbf{Claim~\ref{claim:MOclaim})} shows that \textbf{Algorithm

   \ref{alg:VF2PPPseu})} provides a matching order.

 This section presents the cutting rules of VF2++, which are improved by using extra information coming from the node labels.

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

 by using extra information coming from the node labels.

 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.

 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.

 It has to be shown, that $LabCut_{IND}((u,v),M(s))=true\Rightarrow$ the mapping can not be extended to a whole mapping.\\

 It has to be shown, that $LabCut_{IND}((u,v),M(s))=true\Rightarrow$

 $LabCut_{IND}((u,v),M(s))=true,$ iff the following holds. $\\\exists l: |\Gamma_{large}^{l} (v)\ \cap\ T_{large}(s)| < |\Gamma_{small}^{l} (u)\ \cap\ T_{small}(s)| \vee |\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| < |\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|$.

 the mapping can not be extended to a whole

 mapping.\\ $LabCut_{IND}((u,v),M(s))=true,$ iff the following

 Suppose that $|\Gamma_{large}^{l} (v)\ \cap\ T_{large}(s)| < |\Gamma_{small}^{l} (u)\ \cap\ T_{small}(s)|$. Each node of $\Gamma_{small}^{l} (u)\ \cap\ T_{small}(s)$ has to be matched to a node in $\Gamma_{large}^{l} (v)\ \cap\ T_{large}(s)$, so $\Gamma_{large}^{l} (v)\ \cap\ T_{large}(s)$ can not be smaller than $\Gamma_{small}^{l} (u)\ \cap\ T_{small}(s)$. That is why $M(s)$ can not be extended to a whole mapping.

 holds. $\\\exists l: |\Gamma_{large}^{l} (v)\ \cap\ T_{large}(s)| <

 |\Gamma_{small}^{l} (u)\ \cap\ T_{small}(s)| \vee

 Otherwise $|\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| < |\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|$ has to be true. Similarly, each node of $\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)$ has to be matched to a node in $\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)$, i.e. $\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)$ can not be smaller than $\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)$, if $M(s)$ is extendible.

 |\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| <

 |\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|$.

 Suppose that $|\Gamma_{large}^{l} (v)\ \cap\ T_{large}(s)| <

 |\Gamma_{small}^{l} (u)\ \cap\ T_{small}(s)|$. Each node of

 $\Gamma_{small}^{l} (u)\ \cap\ T_{small}(s)$ has to be matched to a

 node in $\Gamma_{large}^{l} (v)\ \cap\ T_{large}(s)$, so

 $\Gamma_{large}^{l} (v)\ \cap\ T_{large}(s)$ can not be smaller than

 $\Gamma_{small}^{l} (u)\ \cap\ T_{small}(s)$. That is why $M(s)$ can

 not be extended to a whole mapping.

 Otherwise $|\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| <

 |\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|$ has to be

 true. Similarly, each node of $\Gamma_{large}^{l}(v)\cap

 \tilde{T}_{large}(s)$ has to be matched to a node in

 $\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)$,

 i.e. $\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)$ can not be

 smaller than $\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)$, if

 $M(s)$ is extendible.

 This section provides a detailed summary of an efficient implementation of VF2++.

 This section provides a detailed summary of an efficient

 implementation of VF2++.

 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.

 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] = 

  M[i] =

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

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

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

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

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

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

 means "no node".

 Exploring the state space was described in a recursive fashion using sets (see \textbf{Algorithm~\ref{alg:VF2Pseu})}), which makes the algorithm easy to understand but does not show directly an efficient way of implementation. The following approach avoiding recursion and using lookup tables instead of sets is not only fast but has linear space complexity as well.

 Exploring the state space was described in a recursive fashion using

 sets (see \textbf{Algorithm~\ref{alg:VF2Pseu})}), which makes the

 The recursion of \textbf{Algorithm~\ref{alg:VF2Pseu})} can be realized as a while loop, which has a loop counter $depth$ denoting the all-time depth of the recursion.

 algorithm easy to understand but does not show directly an efficient

 Fixing a matching order, let $M$ denote the array storing the all-time mapping.

 way of implementation. The following approach avoiding recursion and

 The initial state is associated with the empty mapping, which means that $\forall i: M[i]=INVALID$ and $depth=0$.

 using lookup tables instead of sets is not only fast but has linear

 In case of a recursive call, $depth$ has to be incremented, while in case of a return, it has to be decremented.

 space complexity as well.

 Based on \textbf{Claim~\ref{claim:claimCoverFromLeft})}, $M$ is $INVALID$ from index $depth$+1 and not $INVALID$ before $depth$, i.e. $\forall i: i < depth \Rightarrow M[i]\neq INVALID$ and $\forall i: i > depth \Rightarrow M[i]= INVALID$. $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 recursion of \textbf{Algorithm~\ref{alg:VF2Pseu})} can be realized

 The necessary part of the candidate set is easily maintainable or computable by following \textbf{Section~\ref{candidateComputingVF2})}. A much faster method has been designed for biological- and sparse graphs, see the next section for details.

 as a 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.  The initial state is

 associated with the empty mapping, which means that $\forall i:

 M[i]=INVALID$ and $depth=0$.  In case of a recursive call, $depth$ has

 to be incremented, while in case of a return, it has to be

 decremented.  Based on \textbf{Claim~\ref{claim:claimCoverFromLeft})},

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

 $depth$, i.e. $\forall i: i < depth \Rightarrow M[i]\neq INVALID$ and

 $\forall i: i > depth \Rightarrow M[i]= INVALID$. $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

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

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

 section for details.

 Being aware of \textbf{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}$.

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

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

 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

 Having said that, an algorithm running in $\Theta(deg)$ time is describable if there exists a covered node in the component containing $u$. In this case choose a covered neighbour $u'$ of $u$ arbitrarily --- such a node exists based on \textbf{Claim~\ref{claim:MOclaim})}. With all the candidates of $u$ being among the uncovered neighbours of $Pair(M,u')$, there are solely $deg(Pair(M,u'))$ nodes to check.

 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

 An easy trick is to choose an $u'$, for which $|\{uncovered\ neighbours\ $ $of\ Pair(M,u')\}|$ is the smallest possible.

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

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

 Note that if $u$ is the first node of its component, then all the uncovered nodes of $G_{large}$ are candidates, so giving a sublinear method is impossible.

 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$. In this case choose a covered neighbour $u'$ of $u$ arbitrarily

 --- such a node exists based on

 \textbf{Claim~\ref{claim:MOclaim})}. With all the candidates of $u$

 being among the uncovered neighbours of $Pair(M,u')$, there are solely

 $deg(Pair(M,u'))$ nodes to check.

 An easy trick is to choose an $u'$, for which

 $|\{uncovered\ neighbours\ $ $of\ Pair(M,u')\}|$ is the smallest

 possible.

 Note that if $u$ is the first node of its component, then all the

 uncovered nodes of $G_{large}$ are candidates, so giving a sublinear

 method is impossible.

 This section describes how the node order preprocessing method of VF2++ can efficiently be implemented.

 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, for which $F_\mathcal{M}[i]=F_\mathcal{M}(i)$ where $i=0,1,..,|K|-1$. At first, $\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.

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

 $\mathcal{M}\subseteq V_{small}$ can be represented as an array of size $|V_{small}|$.

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

 enables $F_\mathcal{M}$ to be stored in an array, for which

 The BFS tree is computed by using a FIFO data structure which is usually implemented as a linked list, but one can avoid it by using the array $\mathcal{M}$ itself. $\mathcal{M}$ contains all the nodes seen before, a pointer shows where the first node of the FIFO is, and another one shows where the next explored node has to be inserted. So the nodes of each level of the BFS tree can be processed by \textbf{Algorithm \ref{alg:VF2PPProcess1})} and \textbf{\ref{alg:VF2PPProcess2})} in place by swapping nodes.

 $F_\mathcal{M}[i]=F_\mathcal{M}(i)$ where $i=0,1,..,|K|-1$. At first,

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

 After a node $u$ gets to the next place of the node order, $F_\mathcal{M}[lab[u]]$ has to be decreased by one, because there is one less covered node in $V_{large}$ with label $lab(u)$, that is why min selection sort is preferred which gives the elements from left to right in descending order, see \textbf{Algorithm \ref{alg:VF2PPProcess1})}.

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

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

 Note that using a $\Theta(n^2)$ sort absolutely does not slow down the procedure on biological (and on sparse) graphs, since they have few nodes on a level. If a level had a large number of nodes, \textbf{Algorithm \ref{alg:VF2PPProcess2})} would seem to be a better choice with a $\Theta(nlog(n))$ or Bucket sort, but it may reduce the efficiency of the matching procedure, since $F_\mathcal{M}(i)$ can not be immediately refreshed, so it is unable to provide up-to-date label information. 

 $\mathcal{M}\subseteq V_{small}$ can be represented as an array of

 Note that the \textit{while loop} of \textbf{Algorithm \ref{alg:VF2PPPseu})} takes one iteration per graph component and the graphs in biology are mostly connected.

 size $|V_{small}|$.

 The BFS tree is computed by using a FIFO data structure which is

 usually implemented as a linked list, but one can avoid it by using

 the array $\mathcal{M}$ itself. $\mathcal{M}$ contains all the nodes

 seen before, a pointer shows where the first node of the FIFO is, and

 another one shows where the next explored node has to be inserted. So

 the nodes of each level of the BFS tree can be processed by

 \textbf{Algorithm \ref{alg:VF2PPProcess1})} and

 \textbf{\ref{alg:VF2PPProcess2})} in place by swapping nodes.

 After a node $u$ gets to the next place of the node order,

 $F_\mathcal{M}[lab[u]]$ has to be decreased by one, because there is

 one less covered node in $V_{large}$ with label $lab(u)$, that is why

 min selection sort is preferred which gives the elements from left to

 right in descending order, see \textbf{Algorithm

   \ref{alg:VF2PPProcess1})}.

 Note that using a $\Theta(n^2)$ sort absolutely does not slow down the

 procedure on biological (and on sparse) graphs, since they have few

 nodes on a level. If a level had a large number of nodes,

 \textbf{Algorithm \ref{alg:VF2PPProcess2})} would seem to be a better

 choice with a $\Theta(nlog(n))$ or Bucket sort, but it may reduce the

 efficiency of the matching procedure, since $F_\mathcal{M}(i)$ can not

 be immediately refreshed, so it is unable to provide up-to-date label

 information.

 Note that the \textit{while loop} of \textbf{Algorithm

   \ref{alg:VF2PPPseu})} takes one iteration per graph component and

 the graphs in biology are mostly connected.

 In \textbf{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.

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

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

 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.

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

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

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

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

 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}$.

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

 Using similar tricks, the consistency function can be evaluated in $\Theta(deg)$ steps, as well.

 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.

 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.

 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

 A short summary of VF2 Plus follows, which uses the notation and the conventions of the original paper.

 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.

 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.

 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.

 $(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}}$. 

 $(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}}$.

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

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

 $V_{large}$

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

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

 $V_{large}$

 $P(u):=P_{lab}(L)*\bigcup_{d'>d}P_{deg}(d')$\\

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

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

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

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

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

 \algtext*{EndFor}%ne nyomtasson ..

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

 \algtext*{EndProcedure}%ne nyomtasson ..

 \Procedure{VF2 Plus order}{}

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

   \State Select the node with the lowest $P$.

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

     \If {more nodes share the same $P$}

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

     \State select the one with maximum degree

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

     \EndIf

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

     \If {more nodes share the same $P$ and have the max degree}

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

     \State select the first

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

     \EndIf

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

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

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

   \State Put all its unsorted neighbours in the set $T$.

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

   \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

 Using these notations, \textbf{Algorithm~\ref{alg:VF2PlusPseu})} provides the description of the sorting procedure.

 Using these notations, \textbf{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.

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

 \newpage

 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.

 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.

 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.

 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 tests have been executed on a recent biological dataset created

 for the International Contest on Pattern Search in Biological

 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.

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

 \\

 Protein and Contact Map graphs extracted from the Protein Data

 Bank\cite{ProteinDataBank}.

 In the following, the induced subgraph isomorphism and the graph isomorphism will be examined.