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

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

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

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

   nevertheless easier to compute - cutting rules significantly

   nevertheless easier to compute - cutting rules significantly

   reducing the search space are applied.

   reducing the search space are applied.

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

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

   Finally, an extensive experimental evaluation is provided using a

   Finally, an extensive experimental evaluation is provided using a

   chemical datasets and standard randomly generated graph series. The

   chemical datasets and standard randomly generated graph series. The

   results show major and consistent running time improvements over the

   results show major and consistent running time improvements over the

   other known methods.

   other known methods.

 \end{abstract}

 \end{abstract}

 \begin{keyword}

 \begin{keyword}

   Computational Biology, Subgraph Isomorphism Problem

   Computational Biology, Subgraph Isomorphism Problem

 Complex biological systems arise from the interaction and cooperation

 Complex biological systems arise from the interaction and cooperation

 of plenty of molecular components. Getting acquainted with such

 of plenty of molecular components. Getting acquainted with such

 systems at the molecular level is of primary importance, since

 systems at the molecular level is of primary importance, since

 protein-protein interaction, DNA-protein interaction, metabolic

 protein-protein interaction, DNA-protein interaction, metabolic

 interaction, transcription factor binding, neuronal networks, and

 interaction, transcription factor binding, neuronal networks, and

 as graphs, for instance, a molecular structure can be

 as graphs, for instance, a molecular structure can be

 considered as a graph, whose nodes correspond to atoms and whose

 considered as a graph, whose nodes correspond to atoms and whose

 edges to chemical bonds. The similarity and dissimilarity of

 edges to chemical bonds. The similarity and dissimilarity of

 objects corresponding to nodes are incorporated to the model

 objects corresponding to nodes are incorporated to the model

 by \emph{node labels}. Understanding such networks basically

 by \emph{node labels}. Understanding such networks basically

 requires finding specific subgraphs, thus it calls for efficient

 requires finding specific subgraphs, thus it calls for efficient

 graph matching algorithms.

 graph matching algorithms.

 Other real-world fields related to some

 Other real-world fields related to some

 variants of graph matching include pattern recognition

 variants of graph matching include pattern recognition

 Subgraph and induced subgraph matching problems are known to be

 Subgraph and induced subgraph matching problems are known to be

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

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

 for various graph classes, like trees and planar

 for various graph classes, like trees and planar

 In the following, some algorithms based on other approaches are

 In the following, some algorithms based on other approaches are

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

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

 an overall polynomial behaviour is not expectable from such an

 an overall polynomial behaviour is not expectable from such an

 alternative, it may often have good practical performance, in fact,

 alternative, it may often have good practical performance, in fact,

 it might be the best choice even on a graph class for which polynomial

 it might be the best choice even on a graph class for which polynomial

 algorithm is known.

 algorithm is known.

 The first practically usable approach was due to

 The first practically usable approach was due to

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

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

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

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

 graphs.

 graphs.

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

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

 the binary Constraint Satisfaction Problem.

 the binary Constraint Satisfaction Problem.

 been considered as one of the fastest graph isomorphism algorithms,

 been considered as one of the fastest graph isomorphism algorithms,

 although graph categories were shown in which it takes exponentially

 although graph categories were shown in which it takes exponentially

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

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

 strategy and formulates the matching as a Constraint Satisfaction

 strategy and formulates the matching as a Constraint Satisfaction

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

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

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

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

 handle new matching types as well.

 handle new matching types as well.

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

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

 it uses some fast executable heuristic checks without using any

 it uses some fast executable heuristic checks without using any

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

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

 coming from biology, and won the International Contest on Pattern

 coming from biology, and won the International Contest on Pattern

 designed for solving pattern matching and computer vision problems,

 designed for solving pattern matching and computer vision problems,

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

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

 a state space representation and checks some conditions in each state

 a state space representation and checks some conditions in each state

 to prune the search tree.

 to prune the search tree.

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

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

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

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

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

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

 significantly faster on practical inputs.

 significantly faster on practical inputs.

 The rest of the paper is structured as

 The rest of the paper is structured as

 follows. Section~\ref{sec:ProbStat} defines the exact problems to be

 follows. Section~\ref{sec:ProbStat} defines the exact problems to be

 solved, Section~\ref{sec:VF2Alg} provides a description of VF2. Based

 solved, Section~\ref{sec:VF2Alg} provides a description of VF2. Based

 on that, Section~\ref{sec:VF2ppAlg} introduces VF2++. Some technical

 on that, Section~\ref{sec:VF2ppAlg} introduces VF2++. Some technical

 details necessary for an efficient implementation are discussed in

 details necessary for an efficient implementation are discussed in

 Section~\ref{sec:VF2ppImpl}.  Finally, Section~\ref{sec:ExpRes}

 Section~\ref{sec:VF2ppImpl}.  Finally, Section~\ref{sec:ExpRes}

 to the state-of-the-art algorithm.

 to the state-of-the-art algorithm.

 It must also be mentioned that the C++ implementations of the

 It must also be mentioned that the C++ implementations of the

 algorithms have been made available for evaluation and use under an

 algorithms have been made available for evaluation and use under an

 library.

 library.

 \section{Problem Statement}\label{sec:ProbStat}

 \section{Problem Statement}\label{sec:ProbStat}

 This section provides a formal description of the problems to be

 This section provides a formal description of the problems to be

 solved.

 solved.

 \end{definition}

 \end{definition}

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

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

 $G_{1}$ isomorphic to any subgraph of $G_{2}$ by a given node

 $G_{1}$ isomorphic to any subgraph of $G_{2}$ by a given node

 label?

 label?

 existence of an induced subgraph.

 existence of an induced subgraph.

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

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

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

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

 \section{The VF2 Algorithm}\label{sec:VF2Alg}

 \section{The VF2 Algorithm}\label{sec:VF2Alg}

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

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

 discussed.

 discussed.

 \subsection{Common notations}

 \subsection{Common notations}

 \indent Assume $G_{1}$ is searched in $G_{2}$.  The following

 \indent Assume $G_{1}$ is searched in $G_{2}$.  The following

 \begin{definition}

 \begin{definition}

 An injection $\mathfrak{m} : D \longrightarrow V_2$ is called (partial) \textbf{mapping}, where $D\subseteq V_1$.

 An injection $\mathfrak{m} : D \longrightarrow V_2$ is called (partial) \textbf{mapping}, where $D\subseteq V_1$.

 \end{definition}

 \end{definition}

 \begin{notation}

 \begin{notation}

 A mapping $\mathfrak{m}$ is $\mathbf{whole\ mapping}$ if $\mathfrak{m}$ covers all the

 A mapping $\mathfrak{m}$ is $\mathbf{whole\ mapping}$ if $\mathfrak{m}$ covers all the

 nodes of $V_{1}$, i.e. $\mathfrak{D}(\mathfrak{m})=V_1$.

 nodes of $V_{1}$, i.e. $\mathfrak{D}(\mathfrak{m})=V_1$.

 \end{definition}

 \end{definition}

 \begin{definition}

 \begin{definition}

 \end{definition}

 \end{definition}

 \begin{notation}

 \begin{notation}

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

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

 \end{notation}

 \end{notation}

 \begin{definition}

 \begin{definition}

 \end{definition}

 \end{definition}

 \begin{definition} 

 \begin{definition} 

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

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

 holds. $\mathbf{Cut_{PT}(\mathfrak{m})}$ is false if there exists a sequence of extend operations, which results in a whole mapping satisfying the requirements of $PT$.

 holds. $\mathbf{Cut_{PT}(\mathfrak{m})}$ is false if there exists a sequence of extend operations, which results in a whole mapping satisfying the requirements of $PT$.

 \end{definition}

 \end{definition}

 \begin{definition}

 \begin{definition}

   $Cons_{PT}(\mathfrak{m})$ is true.

   $Cons_{PT}(\mathfrak{m})$ is true.

 \end{definition}

 \end{definition}

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

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

 \begin{notation}

 \begin{notation}

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

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

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

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

 no whole consistent mapping can contain the current mapping.

 no whole consistent mapping can contain the current mapping.

 \subsection{Overview of the algorithm}

 \subsection{Overview of the algorithm}

 be associated with a mapping $\mathfrak{m}$. The initial state

 be associated with a mapping $\mathfrak{m}$. The initial state

 is associated with a mapping $\mathfrak{m}$, for which

 is associated with a mapping $\mathfrak{m}$, for which

 $\mathfrak{D}(\mathfrak{m})=\emptyset$, i.e. it starts with an empty mapping.

 $\mathfrak{D}(\mathfrak{m})=\emptyset$, i.e. it starts with an empty mapping.

 \Procedure{VF2}{Mapping $\mathfrak{m}$, ProblemType $PT$}

 \Procedure{VF2}{Mapping $\mathfrak{m}$, ProblemType $PT$}

   \If{$\mathfrak{m}$ covers

   \If{$\mathfrak{m}$ covers

     $V_{1}$} \State Output($\mathfrak{m}$)

     $V_{1}$} \State Output($\mathfrak{m}$)

   \Else

   \Else

     $\neg$Cut$_{PT}$($p,\mathfrak{m}$)}

     $\neg$Cut$_{PT}$($p,\mathfrak{m}$)}

     \State \textbf{call}

     \State \textbf{call}

   VF2($extend(\mathfrak{m},p)$, $PT$) \EndIf \EndFor \EndIf \EndProcedure

   VF2($extend(\mathfrak{m},p)$, $PT$) \EndIf \EndFor \EndIf \EndProcedure

 \end{algorithmic}

 \end{algorithmic}

 \end{algorithm}

 \end{algorithm}

 For the current mapping $\mathfrak{m}$, the algorithm computes $P_\mathfrak{m}$, the set of

 For the current mapping $\mathfrak{m}$, the algorithm computes $P_\mathfrak{m}$, the set of

 For each pair $p$ in $P_\mathfrak{m}$, $Cons_{PT}(p,\mathfrak{m})$ and

 For each pair $p$ in $P_\mathfrak{m}$, $Cons_{PT}(p,\mathfrak{m})$ and

 $Cut_{PT}(p,\mathfrak{m})$ are evaluated. If the former is true and

 $Cut_{PT}(p,\mathfrak{m})$ are evaluated. If the former is true and

 the latter is false, the whole process is recursively applied to

 the latter is false, the whole process is recursively applied to

 $extend(\mathfrak{m},p)$. Otherwise, $extend(\mathfrak{m},p)$ is not consistent by $PT$, or it

 $extend(\mathfrak{m},p)$. Otherwise, $extend(\mathfrak{m},p)$ is not consistent by $PT$, or it

 can be proved that $\mathfrak{m}$ can not be extended to a whole mapping.

 can be proved that $\mathfrak{m}$ can not be extended to a whole mapping.

 Through consistent mappings, only consistent whole mappings can be

 Through consistent mappings, only consistent whole mappings can be

 reached, and all the consistent whole mappings are reachable through

 reached, and all the consistent whole mappings are reachable through

 consistent mappings.

 consistent mappings.

 \end{claim}

 \end{claim}

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

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

 order of extensions does not influence the nascent mapping.

 order of extensions does not influence the nascent mapping.

 \begin{claim}

 \begin{claim}

 \label{claim:claimTotOrd}

 \label{claim:claimTotOrd}

 \end{claim}

 \end{claim}

 \subsection{The candidate set}

 \subsection{The candidate set}

 \label{candidateComputingVF2}

 \label{candidateComputingVF2}

 Let $P_\mathfrak{m}$ be the set of the candidate pairs for inclusion in $\mathfrak{m}$.

 Let $P_\mathfrak{m}$ be the set of the candidate pairs for inclusion in $\mathfrak{m}$.

 \begin{notation}

 \begin{notation}

 Let $\mathbf{T_{1}(\mathfrak{m})}:=\{u \in V_{1}\backslash\mathfrak{D}(\mathfrak{m}) : \exists \tilde{u}\in{\mathfrak{D}(\mathfrak{m}): (u,\tilde{u})\in E_{1}}\}$, and

 Let $\mathbf{T_{1}(\mathfrak{m})}:=\{u \in V_{1}\backslash\mathfrak{D}(\mathfrak{m}) : \exists \tilde{u}\in{\mathfrak{D}(\mathfrak{m}): (u,\tilde{u})\in E_{1}}\}$, and

  $\mathbf{T_{2}(\mathfrak{m})} := \{v \in V_{2}\backslash\mathfrak{R}(\mathfrak{m}) : \exists\tilde{v}\in{\mathfrak{R}(\mathfrak{m}):(v,\tilde{v})\in E_{2}}\}$.

  $\mathbf{T_{2}(\mathfrak{m})} := \{v \in V_{2}\backslash\mathfrak{R}(\mathfrak{m}) : \exists\tilde{v}\in{\mathfrak{R}(\mathfrak{m}):(v,\tilde{v})\in E_{2}}\}$.

 \end{notation}

 \end{notation}

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

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

 two uncovered nodes are added. Formally, let

 two uncovered nodes are added. Formally, let

 \[

 \[

  P_\mathfrak{m}\!=\!

  P_\mathfrak{m}\!=\!

   \begin{cases} 

   \begin{cases} 

    &\hspace{-0.15cm}\text{otherwise}.

    &\hspace{-0.15cm}\text{otherwise}.

   \end{cases}

   \end{cases}

 \]

 \]

 \subsection{Consistency}

 \subsection{Consistency}

 $PT$. $Cons_{PT}(p,\mathfrak{m})$ checks whether

 $PT$. $Cons_{PT}(p,\mathfrak{m})$ checks whether

 \begin{notation}

 \begin{notation}

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

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

 (u,\tilde{u})\in E_{1}\}$, and $\mathbf{\Gamma_{2}

 (u,\tilde{u})\in E_{1}\}$, and $\mathbf{\Gamma_{2}

 \end{notation}

 \end{notation}

 \begin{claim}

 \begin{claim}

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

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

 \end{claim}

 \end{claim}

 \subsection{Cutting rules}

 \subsection{Cutting rules}

 $Cut_{PT}(p,\mathfrak{m})$ is defined by a collection of efficiently

 $Cut_{PT}(p,\mathfrak{m})$ is defined by a collection of efficiently

 verifiable conditions. The requirement is that $Cut_{PT}(p,\mathfrak{m})$ can

 verifiable conditions. The requirement is that $Cut_{PT}(p,\mathfrak{m})$ can

 be true only if it is impossible to extend $extend(\mathfrak{m},p)$ to a

 be true only if it is impossible to extend $extend(\mathfrak{m},p)$ to a

 whole mapping.

 whole mapping.

 \begin{notation}

 \begin{notation}

 Let $\mathbf{\tilde{T}_{1}}(\mathfrak{m}):=(V_{1}\backslash

 Let $\mathbf{\tilde{T}_{1}}(\mathfrak{m}):=(V_{1}\backslash

 \mathfrak{D}(\mathfrak{m}))\backslash T_{1}(\mathfrak{m})$, and

 \mathfrak{D}(\mathfrak{m}))\backslash T_{1}(\mathfrak{m})$, and

 \\ $\mathbf{\tilde{T}_{2}}(\mathfrak{m}):=(V_{2}\backslash

 \\ $\mathbf{\tilde{T}_{2}}(\mathfrak{m}):=(V_{2}\backslash

 \mathfrak{R}(\mathfrak{m}))\backslash T_{2}(\mathfrak{m})$.

 \mathfrak{R}(\mathfrak{m}))\backslash T_{2}(\mathfrak{m})$.

 \begin{claim}

 \begin{claim}

 $Cut_{IND}((u,v),\mathfrak{m}):= |\Gamma_{2} (v)\ \cap\ T_{2}(\mathfrak{m})| <

 $Cut_{IND}((u,v),\mathfrak{m}):= |\Gamma_{2} (v)\ \cap\ T_{2}(\mathfrak{m})| <

   |\Gamma_{1} (u)\ \cap\ T_{1}(\mathfrak{m})| \vee |\Gamma_{2}(v)\cap

   |\Gamma_{1} (u)\ \cap\ T_{1}(\mathfrak{m})| \vee |\Gamma_{2}(v)\cap

   \tilde{T}_{2}(\mathfrak{m})| < |\Gamma_{1}(u)\cap

   \tilde{T}_{2}(\mathfrak{m})| < |\Gamma_{1}(u)\cap

 \end{claim}

 \end{claim}

 \section{The VF2++ Algorithm}\label{sec:VF2ppAlg}

 \section{The VF2++ Algorithm}\label{sec:VF2ppAlg}

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

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

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

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

 as possible.

 as possible.

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

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

 introducing more efficient --- nevertheless still easier to compute

 introducing more efficient --- nevertheless still easier to compute

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

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

 designed.

 designed.

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

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

 extendable to handle directed graphs and edge labels as well.

 extendable to handle directed graphs and edge labels as well.

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

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

 the following.\newline

 the following.\newline

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

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

 recognize inconsistency or prune the infeasible branches on the

 recognize inconsistency or prune the infeasible branches on the

 highest levels and goes deep only if it is needed.

 highest levels and goes deep only if it is needed.

 \begin{notation}

 \begin{notation}

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

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

 $H\subseteq V_{1}$.

 $H\subseteq V_{1}$.

 \end{notation}

 \end{notation}

 The principal question is the following. Suppose a mapping $\mathfrak{m}$ is

 The principal question is the following. Suppose a mapping $\mathfrak{m}$ is

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

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

 $T_{1}(\mathfrak{m})$ has --- i.e. the largest $Conn_{\mathfrak{D}(\mathfrak{m})}$ it has

 $T_{1}(\mathfrak{m})$ has --- i.e. the largest $Conn_{\mathfrak{D}(\mathfrak{m})}$ it has

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

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

 are given.

 are given.

 $T_{1}(\mathfrak{m})$ may have the same $Conn_{\mathfrak{D}(\mathfrak{m})}$, which makes

 $T_{1}(\mathfrak{m})$ may have the same $Conn_{\mathfrak{D}(\mathfrak{m})}$, which makes

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

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

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

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

 secondary ordering prefers nodes with the most uncovered neighbours

 secondary ordering prefers nodes with the most uncovered neighbours

 among which have the same $Conn_{\mathfrak{D}(\mathfrak{m})}$ to increase

 among which have the same $Conn_{\mathfrak{D}(\mathfrak{m})}$ to increase

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

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

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

 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

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

 \newline

 \newline

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

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

 described, although they are easily solvable by using a proper

 described, although they are easily solvable by using a proper

 matching order.

 matching order.

 $\mathcal{L}(\tilde{u}):=red \ \forall \tilde{u}\in V_{1}\backslash

 $\mathcal{L}(\tilde{u}):=red \ \forall \tilde{u}\in V_{1}\backslash

 \{u\}$

 \{u\}$

 \newline

 \newline

 $\mathcal{L}(\tilde{v}):=red \ \forall \tilde{v}\in V_{2}\backslash

 $\mathcal{L}(\tilde{v}):=red \ \forall \tilde{v}\in V_{2}\backslash

 \{v\}$

 \{v\}$

 Now, any mapping by $\mathcal{L}$ must contain $(u,v)$, since

 Now, any mapping by $\mathcal{L}$ must contain $(u,v)$, since

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

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

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

 $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

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

 $v$.

 $v$.

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

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

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

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

 precluded in which node labels can not correspond.

 precluded in which node labels can not correspond.

 \end{example}

 \end{example}

 \begin{example}

 \begin{example}

 \newline

 \newline

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

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

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

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

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

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

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

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

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

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

 V_{1}\}$.

 V_{1}\}$.

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

 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

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

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

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

 extended to $G'_{1}$.

 extended to $G'_{1}$.

 \newline

 \newline

 \end{example}

 \end{example}

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

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

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

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

 \begin{notation}

 \begin{notation}

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

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

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

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

 \end{notation}

 \end{notation}

 \end{definition}

 \end{definition}

 \algtext*{EndIf}

 \algtext*{EndIf}

 \algtext*{EndProcedure}

 \algtext*{EndProcedure}

 \algtext*{EndWhile}

 \algtext*{EndWhile}

 \algtext*{EndFor}

 \algtext*{EndFor}

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

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

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

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

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

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

 min$_{F_\mathcal{M}\circ \mathcal{L}}(V_{1}\backslash

 min$_{F_\mathcal{M}\circ \mathcal{L}}(V_{1}\backslash

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

 \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

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

 \EndWhile \EndProcedure

 \EndWhile \EndProcedure

 \end{algorithmic}

 \end{algorithmic}

 \end{algorithm}

 \end{algorithm}

 \begin{algorithm}

 \begin{algorithm}

 \algtext*{EndProcedure}%ne nyomtasson ..

 \algtext*{EndProcedure}%ne nyomtasson ..

 \algtext*{EndWhile}

 \algtext*{EndWhile}

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

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

 \begin{algorithmic}[1]

 \begin{algorithmic}[1]

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

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

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

 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

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

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

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

 \end{algorithmic}

 \end{algorithmic}

 \end{algorithm}

 \end{algorithm}

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

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

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

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

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

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

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

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

 \subsection{Cutting rules}

 \subsection{Cutting rules}

 \label{VF2PPCuttingRules}

 \label{VF2PPCuttingRules}

 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.

 $\mathbf{\Gamma_{2}^{l}(v)}:=\{\tilde{v} : \mathcal{L}(\tilde{v})=l \wedge

 $\mathbf{\Gamma_{2}^{l}(v)}:=\{\tilde{v} : \mathcal{L}(\tilde{v})=l \wedge

 \tilde{v}\in \Gamma_{2} (v)\}$, where $u\in V_{1}$, $v\in

 \tilde{v}\in \Gamma_{2} (v)\}$, where $u\in V_{1}$, $v\in

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

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

 \end{notation}

 \end{notation}

 \end{claim}

 \end{claim}

 \end{claim}

 \end{claim}

 \end{claim}

 \end{claim}

 \section{Implementation details}\label{sec:VF2ppImpl}

 \section{Implementation details}\label{sec:VF2ppImpl}

 This section provides a detailed summary of an efficient

 This section provides a detailed summary of an efficient

 implementation of VF2++.

 implementation of VF2++.

 \subsection{Storing a mapping}

 \subsection{Storing a mapping}

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

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

 the current mapping in the following way.

 the current mapping in the following way.

 \[

 \[

  M[i] =

  M[i] =

   \begin{cases} 

   \begin{cases} 

    v & if\ (u_i,v)\ is\ in\ the\ mapping\\ INV\!ALI\!D &

    v & if\ (u_i,v)\ is\ in\ the\ mapping\\ INV\!ALI\!D &

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

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

   \end{cases}

   \end{cases}

 \]

 \]

 means "no node".

 means "no node".

 \subsection{Avoiding the recurrence}

 \subsection{Avoiding the recurrence}

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

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

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

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

 $M$ is $INV\!ALI\!D$ from index $depth$+1 and not $INV\!ALI\!D$ before

 $M$ is $INV\!ALI\!D$ from index $depth$+1 and not $INV\!ALI\!D$ before

 $depth$. $M[depth]$ changes

 $depth$. $M[depth]$ changes

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

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

 both stepping back to a predecessor state and exploring a successor

 both stepping back to a predecessor state and exploring a successor

 state.

 state.

 The necessary part of the candidate set is easily maintainable or

 The necessary part of the candidate set is easily maintainable or

 computable by following

 computable by following

 section for details.

 section for details.

 \subsection{Calculating the candidates for a node}

 \subsection{Calculating the candidates for a node}

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

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

 case of any of the three problem types and a mapping $\mathfrak{m}$, if a node $v\in

 case of any of the three problem types and a mapping $\mathfrak{m}$, if a node $v\in

 V_{2}$ is a potential pair of $u\in V_{1}$, then $\forall

 V_{2}$ is a potential pair of $u\in V_{1}$, then $\forall

 u'\in \mathfrak{D}(\mathfrak{m}) : (u,u')\in

 u'\in \mathfrak{D}(\mathfrak{m}) : (u,u')\in

 E_{1}\Rightarrow (v,\mathfrak{m}(u'))\in

 E_{1}\Rightarrow (v,\mathfrak{m}(u'))\in

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

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

 describable if there exists a covered node in the component containing

 describable if there exists a covered node in the component containing

 $u$, and a linear one otherwise.

 $u$, and a linear one otherwise.

 \subsection{Determining the node order}

 \subsection{Determining the node order}

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

 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

 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

 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

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

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

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

 \subsection{Cutting rules}

 \subsection{Cutting rules}

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

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

 described using the sets $T_{1}$, $T_{2}$, $\tilde T_{1}$

 described using the sets $T_{1}$, $T_{2}$, $\tilde T_{1}$

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

 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,

 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

 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

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

 $L[\mathcal{L}(u')]$ for all $u'\in \Gamma_{1}(u) \cap T_{1}(\mathfrak{m})$ and

 $L[\mathcal{L}(u')]$ for all $u'\in \Gamma_{1}(u) \cap T_{1}(\mathfrak{m})$ and

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

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

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

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

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

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

 T_{1}$ and $\tilde T_{2}$ instead of $T_{1}$ and

 T_{1}$ and $\tilde T_{2}$ instead of $T_{1}$ and

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

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

 values of $L[\mathcal{L}(u')]$ in case of checking $u$ are dependent only on

 values of $L[\mathcal{L}(u')]$ in case of checking $u$ are dependent only on

 Using similar techniques, the consistency function can be evaluated in

 Using similar techniques, the consistency function can be evaluated in

 \section{Experimental results}\label{sec:ExpRes}

 \section{Experimental results}\label{sec:ExpRes}

 our experience, both algorithms run faster than VF2 with orders of

 our experience, both algorithms run faster than VF2 with orders of

 magnitude, thus its inclusion was not reasonable.

 magnitude, thus its inclusion was not reasonable.

 \subsection{Biological graphs}

 \subsection{Biological graphs}

 The tests have been executed on a recent biological dataset created

 The tests have been executed on a recent biological dataset created

 for the International Contest on Pattern Search in Biological

 for the International Contest on Pattern Search in Biological

 protein and contact map graphs extracted from the Protein Data

 protein and contact map graphs extracted from the Protein Data

 The molecule dataset contains small graphs with less than 100 nodes

 The molecule dataset contains small graphs with less than 100 nodes

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

 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

 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

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

 degree of 20.  \\

 degree of 20.  \\

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

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

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

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

 shuffled, and an isomorphism between the shuffled and the original

 shuffled, and an isomorphism between the shuffled and the original

 \begin{figure}[H]

 \begin{figure}[H]

 \vspace*{-2cm}

 \vspace*{-2cm}

 \hspace*{-1.5cm}

 \hspace*{-1.5cm}

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

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

 \begin{figure}[H]

 \begin{figure}[H]

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

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

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

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

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

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

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

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

 \end{axis}

 \end{axis}

 \end{tikzpicture}

 \end{tikzpicture}

 \end{subfigure}

 \end{subfigure}

 \hspace*{1.5cm}

 \hspace*{1.5cm}

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

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

 \begin{figure}[H]

 \begin{figure}[H]

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

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

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

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

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

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

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

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

         {VF2PPLabel/ContactMaps.128.txt};

         {VF2PPLabel/ContactMaps.128.txt};

 \end{axis}

 \end{axis}

 \end{tikzpicture}

 \end{tikzpicture}

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

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

 \end{figure}

 \end{figure}

 \end{subfigure}

 \end{subfigure}

 \begin{center}

 \begin{center}

 \vspace*{-0.5cm}

 \vspace*{-0.5cm}

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

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

 \begin{figure}[H]

 \begin{figure}[H]

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

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

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

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

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

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

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

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

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

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

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

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

   \end{axis}

   \end{axis}

   \end{tikzpicture}

   \end{tikzpicture}

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

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

   Plus.} \label{fig:INDProt}

   Plus.} \label{fig:INDProt}

 \end{figure}

 \end{figure}

 \end{subfigure}

 \end{subfigure}

 \end{center}

 \end{center}

 \vspace*{-0.5cm}

 \vspace*{-0.5cm}

 \end{figure}

 \end{figure}

 \begin{figure}[H]

 \begin{figure}[H]

 \vspace*{-2cm}

 \vspace*{-2cm}

 \hspace*{-1.5cm}

 \hspace*{-1.5cm}

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

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

 \begin{figure}[H]

 \begin{figure}[H]

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

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

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

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

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

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

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

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

 \end{axis}

 \end{axis}

 \end{tikzpicture}

 \end{tikzpicture}

 \end{figure}

 \end{figure}

 \end{subfigure}

 \end{subfigure}

 \hspace*{1.5cm}

 \hspace*{1.5cm}

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

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

 \begin{figure}[H]

 \begin{figure}[H]

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

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

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

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

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

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

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

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

 \end{axis}

 \end{axis}

 \end{tikzpicture}

 \end{tikzpicture}

 \end{figure}

 \end{figure}

 \end{subfigure}

 \end{subfigure}

 \begin{center}

 \begin{center}

 \vspace*{-0.5cm}

 \vspace*{-0.5cm}

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

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

 \begin{figure}[H]

 \begin{figure}[H]

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

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

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

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

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

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

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

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

 \end{axis}

 \end{axis}

 \end{tikzpicture}

 \end{tikzpicture}

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

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

 \end{figure}

 \end{figure}

 \end{subfigure}

 \end{subfigure}

 \end{center}

 \end{center}

 \vspace*{-0.6cm}

 \vspace*{-0.6cm}

 \end{figure}

 \end{figure}

 \subsection{Random graphs}

 \subsection{Random graphs}

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

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

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

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

 experiments, please see the top of each chart.

 experiments, please see the top of each chart.

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

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

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

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

 on graph sets of various density.

 on graph sets of various density.

 \vspace*{-1.5cm}

 \vspace*{-1.5cm}

 \hspace*{-1.5cm}

 \hspace*{-1.5cm}

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

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

 \begin{center}

 \begin{center}

 \begin{tikzpicture}

 \begin{tikzpicture}

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

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

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

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

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

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

         {randGraph/iso/vf2ppIso5_1.txt};

         {randGraph/iso/vf2ppIso5_1.txt};

 \end{axis}

 \end{axis}

 \end{subfigure}

 \end{subfigure}

 %\hspace{1cm}

 %\hspace{1cm}

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

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

 \begin{center}

 \begin{center}

 \begin{tikzpicture}

 \begin{tikzpicture}

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

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

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

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

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

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

         {randGraph/iso/vf2ppIso10_1.txt};

         {randGraph/iso/vf2ppIso10_1.txt};

 \end{axis}

 \end{axis}

 %%\hspace{1cm}

 %%\hspace{1cm}

 \hspace*{-1.5cm}

 \hspace*{-1.5cm}

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

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

 \begin{center}

 \begin{center}

 \begin{tikzpicture}

 \begin{tikzpicture}

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

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

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

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

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

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

         {randGraph/iso/vf2ppIso15_1.txt};

         {randGraph/iso/vf2ppIso15_1.txt};

 \end{axis}

 \end{axis}

 \end{center}

 \end{center}

      \end{subfigure}

      \end{subfigure}

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

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

 \begin{center}

 \begin{center}

 \begin{tikzpicture}

 \begin{tikzpicture}

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

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

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

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

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

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

         {randGraph/iso/vf2ppIso100_1.txt};

         {randGraph/iso/vf2ppIso100_1.txt};

 \end{axis}

 \end{axis}

 \end{tikzpicture}

 \end{tikzpicture}

 \end{center}

 \end{center}

 \end{subfigure}

 \end{subfigure}

 \vspace*{-0.8cm}

 \vspace*{-0.8cm}

 }\label{fig:randISO}

 }\label{fig:randISO}

 \end{figure}

 \end{figure}

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

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

 has been executed 150 times. Generating a large graph $G_{2}$ of an average degree of $\delta$,

 has been executed 150 times. Generating a large graph $G_{2}$ of an average degree of $\delta$,

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

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

 0.3, 0.8$ cases have been examined, see

 0.3, 0.8$ cases have been examined, see

 \vspace*{-1.5cm}

 \vspace*{-1.5cm}

 \hspace*{-1.5cm}

 \hspace*{-1.5cm}

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

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

 \begin{center}

 \begin{center}

 \begin{tikzpicture}

 \begin{tikzpicture}

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

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

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

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

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

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

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

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

 \end{axis}

 \end{axis}

 \end{center}

 \end{center}

      \end{subfigure}

      \end{subfigure}

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

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

 \begin{center}

 \begin{center}

 \begin{tikzpicture}

 \begin{tikzpicture}

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

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

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

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

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

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

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

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

 \end{axis}

 \end{axis}

 \end{subfigure}

 \end{subfigure}

 \hspace*{-1.5cm}

 \hspace*{-1.5cm}

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

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

 \begin{center}

 \begin{center}

 \begin{tikzpicture}

 \begin{tikzpicture}

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

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

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

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

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

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

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

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

 \end{axis}

 \end{axis}

 \end{center}

 \end{center}

      \end{subfigure}

      \end{subfigure}

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

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

 \begin{center}

 \begin{center}

 \begin{tikzpicture}

 \begin{tikzpicture}

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

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

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

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

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

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

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

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

 \end{axis}

 \end{axis}

 \end{tikzpicture}

 \end{tikzpicture}

 \end{center}

 \end{center}

 \end{subfigure}

 \end{subfigure}

 \vspace*{-0.8cm}

 \vspace*{-0.8cm}

 \end{figure}

 \end{figure}

 \begin{figure}

 \begin{figure}

 \vspace*{-1.5cm}

 \vspace*{-1.5cm}

 \hspace*{-1.5cm}

 \hspace*{-1.5cm}

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

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

 \begin{center}

 \begin{center}

 \hspace*{-0.5cm}

 \hspace*{-0.5cm}

 \begin{tikzpicture}

 \begin{tikzpicture}

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

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

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

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

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

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

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

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

 \end{axis}

 \end{axis}

      \end{subfigure}

      \end{subfigure}

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

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

 \begin{center}

 \begin{center}

      \hspace*{-0.5cm}

      \hspace*{-0.5cm}

 \begin{tikzpicture}

 \begin{tikzpicture}

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

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

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

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

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

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

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

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

 \end{axis}

 \end{axis}

 \end{subfigure}

 \end{subfigure}

 \hspace*{-1.5cm}

 \hspace*{-1.5cm}

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

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

 \begin{center}

 \begin{center}

 \begin{tikzpicture}

 \begin{tikzpicture}

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

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

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

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

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

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

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

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

 \end{axis}

 \end{axis}

 \end{center}

 \end{center}

      \end{subfigure}

      \end{subfigure}

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

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

 \begin{center}

 \begin{center}

 \begin{tikzpicture}

 \begin{tikzpicture}

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

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

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

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

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

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

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

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

 \end{axis}

 \end{axis}

 \end{tikzpicture}

 \end{tikzpicture}

 \end{center}

 \end{center}

 \end{subfigure}

 \end{subfigure}

 \vspace*{-0.8cm}

 \vspace*{-0.8cm}

 \end{figure}

 \end{figure}

 \begin{figure}

 \begin{figure}

 \vspace*{-1.5cm}

 \vspace*{-1.5cm}

 \hspace*{-1.5cm}

 \hspace*{-1.5cm}

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

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

 \begin{center}

 \begin{center}

 \begin{tikzpicture}

 \begin{tikzpicture}

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

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

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

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

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

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

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

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

 \end{axis}

 \end{axis}

 \end{center}

 \end{center}

      \end{subfigure}

      \end{subfigure}

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

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

 \begin{center}

 \begin{center}

 \begin{tikzpicture}

 \begin{tikzpicture}

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

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

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

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

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

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

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

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

 \end{axis}

 \end{axis}

 \end{subfigure}

 \end{subfigure}

 \hspace*{-1.5cm}

 \hspace*{-1.5cm}

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

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

 \begin{center}

 \begin{center}

 \begin{tikzpicture}

 \begin{tikzpicture}

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

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

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

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

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

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

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

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

 \end{axis}

 \end{axis}

 \end{center}

 \end{center}

      \end{subfigure}

      \end{subfigure}

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

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

 \begin{center}

 \begin{center}

 \begin{tikzpicture}

 \begin{tikzpicture}

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

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

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

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

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

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

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

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

 \end{axis}

 \end{axis}

 \end{tikzpicture}

 \end{tikzpicture}

 \end{center}

 \end{center}

 \end{subfigure}

 \end{subfigure}