alpar@0: %% 
alpar@0: %% Copyright 2007, 2008, 2009 Elsevier Ltd
alpar@0: %% 
alpar@0: %% This file is part of the 'Elsarticle Bundle'.
alpar@0: %% ---------------------------------------------
alpar@0: %% 
alpar@0: %% It may be distributed under the conditions of the LaTeX Project Public
alpar@0: %% License, either version 1.2 of this license or (at your option) any
alpar@0: %% later version.  The latest version of this license is in
alpar@0: %%    http://www.latex-project.org/lppl.txt
alpar@0: %% and version 1.2 or later is part of all distributions of LaTeX
alpar@0: %% version 1999/12/01 or later.
alpar@0: %% 
alpar@0: %% The list of all files belonging to the 'Elsarticle Bundle' is
alpar@0: %% given in the file `manifest.txt'.
alpar@0: %% 
alpar@0: 
alpar@0: %% Template article for Elsevier's document class `elsarticle'
alpar@0: %% with numbered style bibliographic references
alpar@0: %% SP 2008/03/01
alpar@0: 
alpar@0: \documentclass[preprint,12pt]{elsarticle}
alpar@0: 
alpar@0: %% Use the option review to obtain double line spacing
alpar@0: %% \documentclass[authoryear,preprint,review,12pt]{elsarticle}
alpar@0: 
alpar@0: %% Use the options 1p,twocolumn; 3p; 3p,twocolumn; 5p; or 5p,twocolumn
alpar@0: %% for a journal layout:
alpar@0: %% \documentclass[final,1p,times]{elsarticle}
alpar@0: %% \documentclass[final,1p,times,twocolumn]{elsarticle}
alpar@0: %% \documentclass[final,3p,times]{elsarticle}
alpar@0: %% \documentclass[final,3p,times,twocolumn]{elsarticle}
alpar@0: %% \documentclass[final,5p,times]{elsarticle}
alpar@0: %% \documentclass[final,5p,times,twocolumn]{elsarticle}
alpar@0: 
alpar@0: %% For including figures, graphicx.sty has been loaded in
alpar@0: %% elsarticle.cls. If you prefer to use the old commands
alpar@0: %% please give \usepackage{epsfig}
alpar@0: 
alpar@0: %% The amssymb package provides various useful mathematical symbols
alpar@0: \usepackage{amssymb}
alpar@0: %% The amsthm package provides extended theorem environments
alpar@0: %% \usepackage{amsthm}
alpar@0: 
alpar@0: %% The lineno packages adds line numbers. Start line numbering with
alpar@0: %% \begin{linenumbers}, end it with \end{linenumbers}. Or switch it on
alpar@0: %% for the whole article with \linenumbers.
alpar@0: %% \usepackage{lineno}
alpar@0: 
alpar@2: \usepackage{amsmath}
alpar@2: %% \usepackage[pdftex]{graphicx}
alpar@2: 
alpar@2: \usepackage{pgfplots}
alpar@2: \pgfplotsset{width=9cm}
alpar@2: \pgfplotsset{compat=1.8}
alpar@2: 
alpar@2: \usepackage{caption}
alpar@2: \usepackage{subcaption} 
alpar@2: 
alpar@2: \usepackage{algorithm}
alpar@2: \usepackage{algpseudocode}
alpar@2: \usepackage{tikz}
alpar@2: 
alpar@2: \usepackage{amsthm,amssymb}
alpar@2: \renewcommand{\qedsymbol}{\rule{0.7em}{0.7em}}
alpar@2: 
alpar@2: \newtheorem{theorem}{Theorem}[subsection]
alpar@2: \newtheorem{corollary}{Corollary}[theorem]
alpar@2: \newtheorem{claim}[theorem]{Claim}
alpar@2: 
alpar@2: \newtheorem{definition}{Definition}[subsection]
alpar@2: \newtheorem{notation}{Notation}[subsection]
alpar@2: \newtheorem{example}{Example}[subsection]
alpar@2: \usetikzlibrary{decorations.markings}
alpar@2: \let\oldproofname=\proofname
alpar@2: %% \renewcommand{\proofname}{\rm\bf{Proof:}}
alpar@2: 
Madarasi@7: \captionsetup{font=normalsize}
Madarasi@7: 
alpar@1: \journal{Discrete Applied Mathematics}
alpar@0: 
alpar@0: \begin{document}
alpar@0: 
alpar@0: \begin{frontmatter}
alpar@0: 
alpar@0: %% Title, authors and addresses
alpar@0: 
alpar@0: %% use the tnoteref command within \title for footnotes;
alpar@0: %% use the tnotetext command for theassociated footnote;
alpar@0: %% use the fnref command within \author or \address for footnotes;
alpar@0: %% use the fntext command for theassociated footnote;
alpar@0: %% use the corref command within \author for corresponding author footnotes;
alpar@0: %% use the cortext command for theassociated footnote;
alpar@0: %% use the ead command for the email address,
alpar@0: %% and the form \ead[url] for the home page:
alpar@0: %% \title{Title\tnoteref{label1}}
alpar@0: %% \tnotetext[label1]{}
alpar@0: %% \author{Name\corref{cor1}\fnref{label2}}
alpar@0: %% \ead{email address}
alpar@0: %% \ead[url]{home page}
alpar@0: %% \fntext[label2]{}
alpar@0: %% \cortext[cor1]{}
alpar@0: %% \address{Address\fnref{label3}}
alpar@0: %% \fntext[label3]{}
alpar@0: 
alpar@24: \title{VF2++ --- An Improved Subgraph Isomorphism Algorithm}
alpar@0: 
alpar@0: %% use optional labels to link authors explicitly to addresses:
alpar@0: %% \author[label1,label2]{}
alpar@0: %% \address[label1]{}
alpar@0: %% \address[label2]{}
alpar@0: 
alpar@24: \author[egres,elte]{Alp{\'a}r J{\"u}ttner}
alpar@24: \ead{alpar@cs.elte.hu}
alpar@24: \author[elte]{P{\'e}ter Madarasi}
alpar@24: \ead{madarasip@caesar.elte.hu}
alpar@24: \address[egres]{MTA-ELTE Egerv{\'a}ry Research Group, Budapest, Hungary.}
alpar@24: \address[elte]{Department of Operations Research, E{\"o}tv{\"o}s Lor{\'a}nd University, Budapest, Hungary.}
alpar@0: 
alpar@0: \begin{abstract}
alpar@0: 
alpar@24:   This paper presents a largely improved version of the VF2 algorithm
alpar@24:   for the \emph{Subgraph Isomorphism Problem}. The improvements are
alpar@24:   twofold. Firstly, it is based on a new approach for determining the
alpar@29:   matching order of the nodes, and secondly, more efficient ---
alpar@29:   nevertheless easier to compute --- cutting rules are proposed. They
alpar@29:   together reduce the search space significantly.
alpar@1: 
Madarasi@28:   In addition to the usual \emph{Subgraph Isomorphism Problem}, the paper also
Madarasi@28:   presents specialized algorithms for the \emph{Induced Subgraph
alpar@24:     Isomorphism} and for the \emph{Graph Isomorphism Problems}.
alpar@1: 
alpar@24:   Finally, an extensive experimental evaluation is provided using a
Madarasi@28:   wide range of inputs, including both real-life biological and
alpar@24:   chemical datasets and standard randomly generated graph series. The
alpar@24:   results show major and consistent running time improvements over the
alpar@24:   other known methods.
alpar@24:  
Madarasi@28:   The C++ implementations of the algorithms are available open-source as 
Madarasi@28:   part of the LEMON graph and network optimization library.
alpar@24:   
alpar@0: \end{abstract}
alpar@0: 
alpar@0: \begin{keyword}
alpar@24:   Computational Biology, Subgraph Isomorphism Problem
alpar@0: %% keywords here, in the form: keyword \sep keyword
alpar@0: 
alpar@0: %% PACS codes here, in the form: \PACS code \sep code
alpar@0: 
alpar@0: %% MSC codes here, in the form: \MSC code \sep code
alpar@0: %% or \MSC[2008] code \sep code (2000 is the default)
alpar@0: 
alpar@0: \end{keyword}
alpar@0: 
alpar@0: \end{frontmatter}
alpar@0: 
alpar@0: %% \linenumbers
alpar@0: 
alpar@0: %% main text
alpar@2: \section{Introduction}
alpar@2: \label{sec:intro}
alpar@2: 
alpar@3: In the last decades, combinatorial structures, and especially graphs
alpar@3: have been considered with ever increasing interest, and applied to the
alpar@29: solution of several new and revised questions. The expressiveness,
alpar@29: the simplicity and the deep theoretical background
alpar@29: of graphs make it one of the most useful
alpar@29: modeling tool and appears constantly in several seemingly independent
Madarasi@19: fields, such as bioinformatics and chemistry.
alpar@2: 
alpar@3: Complex biological systems arise from the interaction and cooperation
alpar@29: of plenty of molecular components. Getting acquainted with the
alpar@29: structure of such systems at the molecular level is of primary
alpar@29: importance, since protein-protein interaction, DNA-protein
alpar@29: interaction, metabolic interaction, transcription factor binding,
alpar@29: neuronal networks, and hormone singling networks can be understood
alpar@29: this way.
alpar@2: 
alpar@29: Many chemical and biological structures can easily be modeled
Madarasi@19: as graphs, for instance, a molecular structure can be
Madarasi@19: considered as a graph, whose nodes correspond to atoms and whose
Madarasi@19: edges to chemical bonds. The similarity and dissimilarity of
Madarasi@19: objects corresponding to nodes are incorporated to the model
Madarasi@19: by \emph{node labels}. Understanding such networks basically
Madarasi@26: requires finding specific subgraphs, thus it calls for efficient
Madarasi@19: graph matching algorithms.
alpar@2: 
Madarasi@19: Other real-world fields related to some
Madarasi@19: variants of graph matching include pattern recognition
Madarasi@28: and machine vision~\cite{HorstBunkeApplications}, symbol recognition~\cite{CordellaVentoSymbolRecognition}, and face identification~\cite{JianzhuangYongFaceIdentification}.  \\
alpar@2: 
alpar@3: Subgraph and induced subgraph matching problems are known to be
Madarasi@28: NP-Complete~\cite{SubgraphNPC}, while the graph isomorphism problem is
alpar@3: one of the few problems in NP neither known to be in P nor
Madarasi@28: NP-Complete. Although polynomial-time isomorphism algorithms are known
alpar@3: for various graph classes, like trees and planar
Madarasi@28: graphs~\cite{PlanarGraphIso}, bounded valence
Madarasi@28: graphs~\cite{BondedDegGraphIso}, interval graphs~\cite{IntervalGraphIso}
alpar@29: or permutation graphs~\cite{PermGraphIso}. Furthermore, an FPT algorithm has also been presented for the colored hypergraph isomorphism problem in~\cite{ColoredHiperGraphIso}.
alpar@2: 
alpar@29: In the following, some algorithms which do not need any restrictions on the graphs are
alpar@29: summarized. Even though,
alpar@29: an overall polynomial behavior is not expectable from such an
alpar@29: alternative, they may often have good practical performance, in fact,
alpar@29: they might be the best choice in practice even on a graph class for which polynomial
Madarasi@19: algorithm is known.
alpar@2: 
alpar@3: The first practically usable approach was due to
Madarasi@28: \emph{Ullmann}~\cite{Ullmann}, which is a commonly used algorithm based on depth-first
Madarasi@28: search with a complex heuristic for reducing the
alpar@3: number of visited states. A major problem is its $\Theta(n^3)$ space
alpar@3: complexity, which makes it impractical in the case of big sparse
alpar@3: graphs.
alpar@2: 
Madarasi@28: In a recent paper, Ullmann~\cite{UllmannBit} presents an
alpar@3: improved version of this algorithm based on a bit-vector solution for
alpar@3: the binary Constraint Satisfaction Problem.
alpar@2: 
Madarasi@28: The \emph{Nauty} algorithm~\cite{Nauty} transforms the two graphs to
alpar@29: a canonical form before starting to look for an isomorphism. It has
alpar@3: been considered as one of the fastest graph isomorphism algorithms,
alpar@3: although graph categories were shown in which it takes exponentially
alpar@3: many steps. This algorithm handles only the graph isomorphism problem.
alpar@2: 
Madarasi@28: The \emph{LAD} algorithm~\cite{Lad} uses a depth-first search
alpar@3: strategy and formulates the matching as a Constraint Satisfaction
alpar@3: Problem to prune the search tree. The constraints are that the mapping
alpar@29: has to be invective and edge-preserving, hence it is possible to
alpar@3: handle new matching types as well.
alpar@2: 
Madarasi@28: The \emph{RI} algorithm~\cite{RI} and its variations are based on a
alpar@3: state space representation. After reordering the nodes of the graphs,
alpar@3: it uses some fast executable heuristic checks without using any
alpar@3: complex pruning rules. It seems to run really efficiently on graphs
alpar@3: coming from biology, and won the International Contest on Pattern
Madarasi@28: Search in Biological Databases~\cite{Content}.
alpar@2: 
Madarasi@28: Currently, the most commonly used algorithm is the
alpar@29: \emph{VF2}~\cite{VF2}, an improved version of \emph{VF}~\cite{VF}, which was
alpar@3: designed for solving pattern matching and computer vision problems,
alpar@3: and has been one of the best overall algorithms for more than a
Madarasi@28: decade. Although, it is not as fast as some of the new specialized algorithms, it is still widely used due to its simplicity and space efficiency. VF2 uses
alpar@29: a state space representation and checks specific conditions in each state
alpar@3: to prune the search tree.
alpar@2: 
Madarasi@28: Meanwhile, another variant called \emph{VF2~Plus}~\cite{VF2Plus} has
alpar@3: been published. It is considered to be as efficient as the RI
alpar@29: algorithm and has a strictly better behavior on large graphs.  The
alpar@29: main idea of VF2~Plus is to precompute a heuristic node order of the graph to be embedded, on which VF2 works more efficiently.
alpar@2: 
Madarasi@19: This paper introduces \emph{VF2++}, a new further improved algorithm
alpar@29: for the graph and (induced) subgraph isomorphism problems. It is based on
Madarasi@19: efficient cutting rules and determines a node order in which VF2 runs
Madarasi@19: significantly faster on practical inputs.
Madarasi@19: 
alpar@25: The rest of the paper is structured as
alpar@25: follows. Section~\ref{sec:ProbStat} defines the exact problems to be
alpar@25: solved, Section~\ref{sec:VF2Alg} provides a description of VF2. Based
alpar@25: on that, Section~\ref{sec:VF2ppAlg} introduces VF2++. Some technical
alpar@25: details necessary for an efficient implementation are discussed in
alpar@29: Section~\ref{sec:VF2ppImpl}. Finally, Section~\ref{sec:ExpRes}
Madarasi@28: provides a detailed experimental evaluation of VF2++ and its comparison
alpar@27: to the state-of-the-art algorithm.
Madarasi@26: 
alpar@25: It must also be mentioned that the C++ implementations of the
alpar@25: algorithms have been made available for evaluation and use under an
alpar@29: open-source license as a part of
alpar@29: LEMON~\cite{o11:_lemon_open_sourc_c_graph_templ_librar} graph library.
Madarasi@22: 
Madarasi@22: \section{Problem Statement}\label{sec:ProbStat}
Madarasi@19: This section provides a formal description of the problems to be
alpar@3: solved.
alpar@2: \subsection{Definitions}
alpar@2: 
Madarasi@19: Throughout the paper $G_{1}=(V_{1}, E_{1})$ and
Madarasi@19: $G_{2}=(V_{2}, E_{2})$ denote two undirected graphs.
Madarasi@19: 
Madarasi@19: \begin{definition}
Madarasi@19: $\mathcal{L}: (V_{1}\cup V_{2}) \longrightarrow K$ is a \textbf{node
Madarasi@19:     label function}, where K is an arbitrary set. The elements in K
Madarasi@19:   are the \textbf{node labels}. Two nodes, u and v are said to be
Madarasi@19:   \textbf{equivalent} if $\mathcal{L}(u)=\mathcal{L}(v)$.
Madarasi@19: \end{definition}
Madarasi@19: 
alpar@29: For the sake of simplicity, the graph, subgraph and induced subgraph
alpar@29: isomorphisms are defined in a more general way.
Madarasi@19: 
alpar@2: \begin{definition}\label{sec:ismorphic}
Madarasi@19: $G_{1}$ and $G_{2}$ are \textbf{isomorphic} (by the node label $\mathcal{L}$) if $\exists \mathfrak{m}:
Madarasi@19:   V_{1} \longrightarrow V_{2}$ bijection, for which the
alpar@3:   following is true:
alpar@2: \begin{center}
Madarasi@20: $\forall u\in{V_{1}} : \mathcal{L}(u)=\mathcal{L}(\mathfrak{m}(u))$ and\\
Madarasi@19: $\forall u,v\in{V_{1}} : (u,v)\in{E_{1}} \Leftrightarrow (\mathfrak{m}(u),\mathfrak{m}(v))\in{E_{2}}$
alpar@2: \end{center}
alpar@2: \end{definition}
Madarasi@19: 
alpar@2: \begin{definition}
Madarasi@19: $G_{1}$ is a \textbf{subgraph} of $G_{2}$ (by the node label $\mathcal{L}$) if $\exists \mathfrak{m}:
Madarasi@19:   V_{1}\longrightarrow V_{2}$ injection, for which the
alpar@3:   following is true:
alpar@2: \begin{center}
Madarasi@20: $\forall u\in{V_{1}} : \mathcal{L}(u)=\mathcal{L}(\mathfrak{m}(u))$ and\\
Madarasi@19: $\forall u,v \in{V_{1}} : (u,v)\in{E_{1}} \Rightarrow (\mathfrak{m}(u),\mathfrak{m}(v))\in E_{2}$
alpar@2: \end{center}
alpar@2: \end{definition}
alpar@2: 
alpar@2: \begin{definition} 
Madarasi@19: $G_{1}$ is an \textbf{induced subgraph} of $G_{2}$ (by the node label $\mathcal{L}$) if $\exists
Madarasi@19:   \mathfrak{m}: V_{1}\longrightarrow V_{2}$ injection, for which the
alpar@3:   following is true:
alpar@2: \begin{center}
Madarasi@19: $\forall u\in{V_{1}} : \mathcal{L}(u)=\mathcal{L}(\mathfrak{m}(u))$ and
Madarasi@19: 
Madarasi@19: $\forall u,v \in{V_{1}} : (u,v)\in{E_{1}} \Leftrightarrow
Madarasi@19:   (\mathfrak{m}(u),\mathfrak{m}(v))\in E_{2}$
alpar@2: \end{center}
alpar@2: \end{definition}
alpar@2: 
alpar@2: 
alpar@2: \subsection{Common problems}\label{sec:CommProb}
alpar@2: 
Madarasi@28: The focus of this paper is on the following problems appearing in many applications.
alpar@2: 
Madarasi@28: The \textbf{subgraph isomorphism problem} is the following: is
Madarasi@19: $G_{1}$ isomorphic to any subgraph of $G_{2}$ by a given node
alpar@3: label?
alpar@2: 
Madarasi@28: The \textbf{induced subgraph isomorphism problem} asks the same about the
alpar@3: existence of an induced subgraph.
alpar@2: 
alpar@3: The \textbf{graph isomorphism problem} can be defined as induced
alpar@3: subgraph matching problem where the sizes of the two graphs are equal.
alpar@2: 
alpar@29: In addition, one may either want to find a \textbf{single} embedding or \textbf{enumerate} all of them.
alpar@2: 
Madarasi@22: \section{The VF2 Algorithm}\label{sec:VF2Alg}
Madarasi@28: This algorithm is the basis of both the VF2++ and the VF2~Plus.  VF2
Madarasi@28: is able to handle all the variations mentioned in Section~\ref{sec:CommProb}.  Although it can also handle directed graphs,
alpar@29: for the sake of simplicity, only the undirected case is
alpar@3: discussed.
alpar@2: 
alpar@2: 
alpar@2: \subsection{Common notations}
Madarasi@19: \indent Assume $G_{1}$ is searched in $G_{2}$.  The following
alpar@29: definitions and notations is used throughout this paper.
alpar@2: \begin{definition}
Madarasi@19: An injection $\mathfrak{m} : D \longrightarrow V_2$ is called (partial) \textbf{mapping}, where $D\subseteq V_1$.
Madarasi@19: \end{definition}
Madarasi@19: 
Madarasi@19: \begin{notation}
Madarasi@19: $\mathfrak{D}(f)$ and $\mathfrak{R}(f)$ denote the domain and the range of a function $f$, respectively.
Madarasi@19: \end{notation}
Madarasi@19: 
Madarasi@19: \begin{definition}
Madarasi@19: Mapping $\mathfrak{m}$ \textbf{covers} a node $u\in V_1\cup V_2$ if $u\in \mathfrak{D}(\mathfrak{m})\cup \mathfrak{R}(\mathfrak{m})$.
alpar@2: \end{definition}
alpar@2: 
alpar@2: \begin{definition}
Madarasi@19: A mapping $\mathfrak{m}$ is $\mathbf{whole\ mapping}$ if $\mathfrak{m}$ covers all the
Madarasi@19: nodes of $V_{1}$, i.e. $\mathfrak{D}(\mathfrak{m})=V_1$.
alpar@2: \end{definition}
alpar@2: 
alpar@2: \begin{definition}
Madarasi@28: Let \textbf{extend}$(\mathfrak{m},(u,v))$ denote the function $f : \mathfrak{D}(\mathfrak{m})\cup\{u\}\longrightarrow\mathfrak{R}(\mathfrak{m})\cup\{v\}$, for which $\forall w\in \mathfrak{D}(\mathfrak{m}) : f(w)=\mathfrak{m}(w)$ and $f(u)=v$ holds, where $u\in V_1\setminus\mathfrak{D}(\mathfrak{m})$ and $v\in V_2\setminus\mathfrak{R}(\mathfrak{m})$; otherwise $extend(\mathfrak{m},(u,v))$ is undefined.
alpar@2: \end{definition}
alpar@2: 
alpar@2: \begin{notation}
Madarasi@19: Throughout the paper, $\mathbf{PT}$ denotes a generic problem type
Madarasi@28: which can be substituted by any of the $\mathbf{SUB}$, $\mathbf{IND}$
alpar@29: and $\mathbf{ISO}$ problems, which stand for the problems mentioned in Section~\ref{sec:CommProb} respectively.
alpar@2: \end{notation}
alpar@2: 
alpar@2: \begin{definition}
Madarasi@28: Let $\mathfrak{m}$ be a mapping. The \textbf{consistency function for } $\mathbf{PT}$ is a logical function, for which $\mathbf{Cons_{PT}}(\mathfrak{m})$ is true if and only if $\mathfrak{m}$ satisfies the requirements of $\mathbf{PT}$ considering the subgraphs of $G_{1}$ and $G_{2}$ induced by $\mathfrak{D}(\mathfrak{m})$ and $\mathfrak{R}(\mathfrak{m})$, respectively.
Madarasi@28: 
Madarasi@28: %$\mathbf{Cons_{PT}}(\mathfrak{m})$ is true if there exists a whole mapping $w$ satisfying the requirements of $PT$, for which $\mathfrak{m}$ is exactly $w$ restricted to $\mathfrak{D}(\mathfrak{m})$.
alpar@2: \end{definition}
alpar@2: 
alpar@2: \begin{definition} 
Madarasi@19: Let $\mathfrak{m}$ be a mapping. A logical function $\mathbf{Cut_{PT}}$ is a
Madarasi@28: \textbf{cutting function for } $\mathbf{PT}$ if the following
Madarasi@19: 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$.
alpar@2: \end{definition}
alpar@2: 
alpar@2: \begin{definition}
Madarasi@28: A mapping $\mathfrak{m}$ is said to be \textbf{consistent mapping by} $\mathbf{PT}$ if
Madarasi@19:   $Cons_{PT}(\mathfrak{m})$ is true.
alpar@2: \end{definition}
alpar@2: 
alpar@2: $Cons_{PT}$ and $Cut_{PT}$ will often be used in the following form.
alpar@2: \begin{notation}
Madarasi@19: Let $\mathbf{Cons_{PT}(p, \mathfrak{m})}:=Cons_{PT}(extend(\mathfrak{m},p))$, and
Madarasi@19: $\mathbf{Cut_{PT}(p, \mathfrak{m})}:=Cut_{PT}(extend(\mathfrak{m},p))$, where
Madarasi@19: $p\in{V_{1}\backslash\mathfrak{D}(\mathfrak{m}) \!\times\!V_{2}\backslash\mathfrak{R}(\mathfrak{m})}$.
alpar@2: \end{notation}
alpar@2: 
alpar@3: $Cons_{PT}$ will be used to check the consistency of the already
alpar@3: covered nodes, while $Cut_{PT}$ is for looking ahead to recognize if
alpar@3: no whole consistent mapping can contain the current mapping.
alpar@2: 
alpar@2: \subsection{Overview of the algorithm}
alpar@2: 
Madarasi@28: VF2 begins with an empty mapping and gradually extends it with respect to the consistency and cutting functions until a whole mapping is reached.
Madarasi@28: 
Madarasi@28: Algorithm~\ref{alg:VF2Pseu} is a high-level description of
Madarasi@28: the VF2 algorithm. Each state of the matching process can
Madarasi@19: be associated with a mapping $\mathfrak{m}$. The initial state
Madarasi@19: is associated with a mapping $\mathfrak{m}$, for which
Madarasi@19: $\mathfrak{D}(\mathfrak{m})=\emptyset$, i.e. it starts with an empty mapping.
alpar@2: 
alpar@2: 
alpar@2: \begin{algorithm}
Madarasi@13: \algtext*{EndIf}%ne nyomtasson end if-et
Madarasi@13: \algtext*{EndFor}%ne
Madarasi@13: \algtext*{EndProcedure}%ne nyomtasson ..
alpar@2: \caption{\hspace{0.5cm}$A\ high\ level\ description\ of\ VF2$}\label{alg:VF2Pseu}
alpar@2: \begin{algorithmic}[1]
alpar@2: 
Madarasi@19: \Procedure{VF2}{Mapping $\mathfrak{m}$, ProblemType $PT$}
Madarasi@19:   \If{$\mathfrak{m}$ covers
Madarasi@19:     $V_{1}$} \State Output($\mathfrak{m}$)
Madarasi@19:   \Else
Madarasi@28:   \State Compute the set $P_\mathfrak{m}$ of the candidate pairs for extending $\mathfrak{m}$ \ForAll{$p\in{P_\mathfrak{m}}$} \If{Cons$_{PT}$($p,\mathfrak{m}$) $\wedge$
Madarasi@19:     $\neg$Cut$_{PT}$($p,\mathfrak{m}$)}
Madarasi@19:     \State \textbf{call}
Madarasi@19:   VF2($extend(\mathfrak{m},p)$, $PT$) \EndIf \EndFor \EndIf \EndProcedure
alpar@2: \end{algorithmic}
alpar@2: \end{algorithm}
alpar@2: 
alpar@2: 
Madarasi@19: For the current mapping $\mathfrak{m}$, the algorithm computes $P_\mathfrak{m}$, the set of
Madarasi@28: candidate node pairs for extending the current mapping $\mathfrak{m}$.
alpar@2: 
Madarasi@19: For each pair $p$ in $P_\mathfrak{m}$, $Cons_{PT}(p,\mathfrak{m})$ and
Madarasi@19: $Cut_{PT}(p,\mathfrak{m})$ are evaluated. If the former is true and
Madarasi@19: the latter is false, the whole process is recursively applied to
Madarasi@19: $extend(\mathfrak{m},p)$. Otherwise, $extend(\mathfrak{m},p)$ is not consistent by $PT$, or it
Madarasi@19: can be proved that $\mathfrak{m}$ can not be extended to a whole mapping.
alpar@2: 
alpar@29: The correctness of the procedure follows from the claim below.
alpar@29: 
Madarasi@28: \begin{claim}\label{claim:consMapps}
alpar@3: Through consistent mappings, only consistent whole mappings can be
Madarasi@19: reached, and all the consistent whole mappings are reachable through
alpar@3: consistent mappings.
alpar@2: \end{claim}
alpar@2: 
Madarasi@19: Note that a mapping may be reached in exponentially many different ways, since the
Madarasi@19: order of extensions does not influence the nascent mapping.
alpar@2: 
Madarasi@28: However, one may make the following observations.
Madarasi@28: 
Madarasi@28: %\begin{claim}
Madarasi@28: %\label{claim:claimTotOrd}
Madarasi@28: %Let $\prec$ be an arbitrary total ordering relation on $V_{1}$.  If
Madarasi@28: %the algorithm ignores each $p=(u,v) \in P_\mathfrak{m}$, for which
Madarasi@28: %\begin{center}
Madarasi@28: %$\exists (\tilde{u},\tilde{v})\in P_\mathfrak{m}: \tilde{u} \prec u$,
Madarasi@28: %\end{center}
Madarasi@28: %then no mapping can be reached more than once, and each whole mapping %remains reachable.
Madarasi@28: %\end{claim}
Madarasi@28: 
Madarasi@28: \begin{definition}
Madarasi@28: A total order $(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{1}|)})$ of
Madarasi@28: $V_{1}$ is \textbf{matching order} if VF2 can cover $u_{\sigma(d)}$ on the $d$-th level for all $d\in\{1,..,|V_{1}|\}$.
Madarasi@28: \end{definition}
alpar@2: 
alpar@2: \begin{claim}
alpar@2: \label{claim:claimTotOrd}
Madarasi@28: If VF2 is prescribed to cover the nodes of $G_1$ according to a matching order, then no mapping can be reached more than once and each whole mapping remains reachable.
alpar@2: \end{claim}
alpar@2: 
Madarasi@28: Note that the cornerstone of the improvements to VF2 is to choose a proper
Madarasi@28: matching order.
alpar@2: 
Madarasi@19: \subsection{The candidate set}
alpar@2: \label{candidateComputingVF2}
Madarasi@19: Let $P_\mathfrak{m}$ be the set of the candidate pairs for inclusion in $\mathfrak{m}$.
alpar@2: 
alpar@2: \begin{notation}
Madarasi@19: 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
Madarasi@19:  $\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}}\}$.
alpar@2: \end{notation}
alpar@2: 
Madarasi@28: The set $P_\mathfrak{m}$ contains the pairs of uncovered neighbours of covered
Madarasi@17: nodes, and if there is not such a node pair, all the pairs containing
alpar@3: two uncovered nodes are added. Formally, let
alpar@2: \[
Madarasi@19:  P_\mathfrak{m}\!=\!
alpar@2:   \begin{cases} 
Madarasi@19:    T_{1}(\mathfrak{m})\times T_{2}(\mathfrak{m})&\hspace{-0.15cm}\text{if }
Madarasi@19:    T_{1}(\mathfrak{m})\!\neq\!\emptyset\ \text{and }T_{2}(\mathfrak{m})\!\neq
Madarasi@19:    \emptyset,\\ (V_{1}\!\setminus\!\mathfrak{D}(\mathfrak{m}))\!\times\!(V_{2}\!\setminus\!\mathfrak{R}(\mathfrak{m}))
Madarasi@19:    &\hspace{-0.15cm}\text{otherwise}.
alpar@2:   \end{cases}
alpar@2: \]
alpar@2: 
alpar@2: \subsection{Consistency}
Madarasi@28: Let $p=(u,v)\in V_{1}\times V_{2}$, and suppose $\mathfrak{m}$ is a consistent mapping by
Madarasi@19: $PT$. $Cons_{PT}(p,\mathfrak{m})$ checks whether
Madarasi@28: adding pair $p$ into $\mathfrak{m}$ leads to a consistent mapping by $PT$.
Madarasi@15: 
Madarasi@28: For example, the consistency function of the induced subgraph isomorphism problem is the following.
alpar@2: \begin{notation}
Madarasi@19: Let $\mathbf{\Gamma_{1} (u)}:=\{\tilde{u}\in V_{1} :
Madarasi@19: (u,\tilde{u})\in E_{1}\}$, and $\mathbf{\Gamma_{2}
Madarasi@28:   (v)}:=\{\tilde{v}\in V_{2} : (v,\tilde{v})\in E_{2}\}$, where $u\in V_{1}$ and $v\in V_{2}$. That is, $\mathbf{\Gamma_{i} (w)}$ denotes the set of neighbours of node $w$ in $G_i$ $(i=1,2)$.
alpar@2: \end{notation}
alpar@2: 
alpar@2: \begin{claim}
Madarasi@28: $extend(\mathfrak{m},(u,v))$ is a consistent mapping by $IND$ if and only if $\mathfrak{m}$ is consistent and $(\forall \tilde{u}\in \mathfrak{D}(\mathfrak{m}): (u,\tilde{u})\in E_{1}
Madarasi@28: \Leftrightarrow (v,\mathfrak{m}(\tilde{u}))\in E_{2})$. 
Madarasi@28: \end{claim}
Madarasi@28: 
Madarasi@28: The following formulation gives an efficient way of calculating $Cons_{IND}$.
Madarasi@28: 
Madarasi@28: \begin{claim}
Madarasi@28: $Cons_{IND}((u,v),\mathfrak{m}):=Cons_{IND}(\mathfrak{m})\wedge\mathcal{L}(u)\!\!=\!\!\mathcal{L}(v)\wedge(\forall \tilde{v}\in \Gamma_{2}(v)\cap\mathfrak{R}(\mathfrak{m}):(u,\mathfrak{m}^{-1}(\tilde{v}))\in E_{1})\wedge
Madarasi@19:   (\forall \tilde{u}\in \Gamma_{1}(u)
Madarasi@28:   \cap \mathfrak{D}(\mathfrak{m}):(v,\mathfrak{m}(\tilde{u}))\in E_{2})$ is the consistency function for $IND$.
alpar@2: \end{claim}
alpar@2: 
alpar@2: \subsection{Cutting rules}
Madarasi@19: $Cut_{PT}(p,\mathfrak{m})$ is defined by a collection of efficiently
Madarasi@19: verifiable conditions. The requirement is that $Cut_{PT}(p,\mathfrak{m})$ can
Madarasi@19: be true only if it is impossible to extend $extend(\mathfrak{m},p)$ to a
alpar@3: whole mapping.
Madarasi@15: 
Madarasi@28: As an example, a cutting function of induced subgraph isomorphism problem is presented.
alpar@2: \begin{notation}
Madarasi@19: Let $\mathbf{\tilde{T}_{1}}(\mathfrak{m}):=(V_{1}\backslash
Madarasi@19: \mathfrak{D}(\mathfrak{m}))\backslash T_{1}(\mathfrak{m})$, and
Madarasi@19: \\ $\mathbf{\tilde{T}_{2}}(\mathfrak{m}):=(V_{2}\backslash
Madarasi@19: \mathfrak{R}(\mathfrak{m}))\backslash T_{2}(\mathfrak{m})$.
alpar@2: \end{notation}
Madarasi@15: 
alpar@2: \begin{claim}
Madarasi@19: $Cut_{IND}((u,v),\mathfrak{m}):= |\Gamma_{2} (v)\ \cap\ T_{2}(\mathfrak{m})| <
Madarasi@19:   |\Gamma_{1} (u)\ \cap\ T_{1}(\mathfrak{m})| \vee |\Gamma_{2}(v)\cap
Madarasi@19:   \tilde{T}_{2}(\mathfrak{m})| < |\Gamma_{1}(u)\cap
Madarasi@28:   \tilde{T}_{1}(\mathfrak{m})|$ is a cutting function for $IND$.
alpar@2: \end{claim}
alpar@2: 
Madarasi@22: \section{The VF2++ Algorithm}\label{sec:VF2ppAlg}
Madarasi@28: Although any matching order makes the search space of VF2 a
alpar@3: tree, its choice turns out to dramatically influence the number of
alpar@3: visited states. The goal is to determine an efficient one as quickly
alpar@3: as possible.
alpar@2: 
Madarasi@28: The main reason for the superiority of VF2++ over VF2 is twofold. Firstly,
alpar@29: taking into account the structure and the node labeling of the graph,
Madarasi@28: VF2++ determines a matching order in which most of the unfruitful
alpar@3: branches of the search space can be pruned immediately. Secondly,
alpar@3: introducing more efficient --- nevertheless still easier to compute
alpar@3: --- cutting rules reduces the chance of going astray even further.
alpar@2: 
Madarasi@28: In addition to the usual subgraph isomorphism problem, specialized versions
alpar@29: for induced subgraph and graph isomorphism problems have also been
Madarasi@22: designed.
alpar@2: 
Madarasi@28: Note that a weaker version of the cutting rules of VF2++ and an efficient
Madarasi@28: candidate set calculation method were described in~\cite{VF2Plus}.
alpar@2: 
alpar@3: It should be noted that all the methods described in this section are
Madarasi@22: extendable to handle directed graphs and edge labels as well.
alpar@3: The basic ideas and the detailed description of VF2++ are provided in
Madarasi@22: the following.\newline
alpar@2: 
Madarasi@19: The goal is to find a matching order in which the algorithm is able to
Madarasi@19: recognize inconsistency or prune the infeasible branches on the
Madarasi@19: highest levels and goes deep only if it is needed.
Madarasi@19: 
Madarasi@19: \begin{notation}
Madarasi@28: Let $\mathbf{Conn_{H}(u)}:=|\Gamma_{1}(u)\cap H|$, that is the
Madarasi@19: number of neighbours of u which are in H, where $u\in V_{1} $ and
Madarasi@19: $H\subseteq V_{1}$.
Madarasi@19: \end{notation}
Madarasi@19: 
Madarasi@19: The principal question is the following. Suppose a mapping $\mathfrak{m}$ is
Madarasi@19: given. For which node of $T_{1}(\mathfrak{m})$ is the hardest to find a
alpar@29: consistent pair in $G_{2}$? The more covered neighbors a node in
Madarasi@19: $T_{1}(\mathfrak{m})$ has --- i.e. the largest $Conn_{\mathfrak{D}(\mathfrak{m})}$ it has
alpar@29: ---, the more rare-to-satisfy consistency constraints for its pair
Madarasi@19: are given.
Madarasi@19: 
Madarasi@28: Most of the graphs of biological and chemical structures are sparse, thus several nodes in
Madarasi@19: $T_{1}(\mathfrak{m})$ may have the same $Conn_{\mathfrak{D}(\mathfrak{m})}$, which makes
Madarasi@19: reasonable to define a secondary and a tertiary order between them.
Madarasi@19: The observation above proves itself to be as determining, that the
alpar@29: secondary ordering prefers nodes with the most uncovered neighbors
Madarasi@19: among which have the same $Conn_{\mathfrak{D}(\mathfrak{m})}$ to increase
Madarasi@28: $Conn_{\mathfrak{D}(\mathfrak{m})}$ of uncovered nodes as much, as possible.  The tertiary ordering prefers nodes having the rarest uncovered labels in $G_2$.
Madarasi@19: 
Madarasi@28: Note that the secondary ordering is the same as ordering by degrees,
Madarasi@19: which is a static data in front of the above used.
Madarasi@19: 
Madarasi@19: These rules can easily result in a matching order which contains the
Madarasi@19: nodes of a long path successively, whose nodes may have low $Conn$ and
alpar@29: is easily to match into $G_{2}$. To try to avoid that, a
alpar@29: Breadth-First-Search order is used, and on each of its levels, the
alpar@29: ordering procedure described above is applied.
Madarasi@19: \newline
Madarasi@19: 
alpar@29: In the following, examples are shown, demonstrating that VF2 may be
alpar@29: slow are, even though a matching can be found easily by using a proper
Madarasi@19: matching order.
Madarasi@19: 
Madarasi@19: \begin{example}
Madarasi@19: Suppose $G_{1}$ can be mapped into $G_{2}$ in many ways
Madarasi@19: without node labels. Let $u\in V_{1}$ and $v\in V_{2}$.
Madarasi@19: \newline
Madarasi@19: $\mathcal{L}(u):=black$
Madarasi@19: \newline
Madarasi@19: $\mathcal{L}(v):=black$
Madarasi@19: \newline
Madarasi@22: $\mathcal{L}(\tilde{u}):=red \ \forall \tilde{u}\in V_{1}\backslash
Madarasi@22: \{u\}$
Madarasi@19: \newline
Madarasi@22: $\mathcal{L}(\tilde{v}):=red \ \forall \tilde{v}\in V_{2}\backslash
Madarasi@22: \{v\}$
Madarasi@19: 
Madarasi@19: Now, any mapping by $\mathcal{L}$ must contain $(u,v)$, since
Madarasi@19: $u$ is black and no node in $V_{2}$ has a black label except
Madarasi@19: $v$. If unfortunately $u$ were the last node which will get covered,
Madarasi@19: VF2 would check only in the last steps, whether $u$ can be matched to
Madarasi@19: $v$.
Madarasi@28: 
alpar@29: However, had $u$ been the first matched node, $u$ would have been
alpar@29: matched immediately to $v$, so all the mappings would have been
Madarasi@19: precluded in which node labels can not correspond.
Madarasi@19: \end{example}
Madarasi@19: 
Madarasi@19: \begin{example}
Madarasi@28: Suppose there is no node label given, and $G_{1}$ is a small graph that can not be mapped into $G_{2}$ and $u\in V_{1}$.
Madarasi@19: \newline
Madarasi@19: Let $G'_{1}:=(V_{1}\cup
Madarasi@19: \{u'_{1},u'_{2},..,u'_{k}\},E_{1}\cup
Madarasi@19: \{(u,u'_{1}),(u'_{1},u'_{2}),..,(u'_{k-1},u'_{k})\})$, that is,
Madarasi@19: $G'_{1}$ is $G_{1}\cup \{ a\ k$ long path, which is disjoint
Madarasi@19: from $G_{1}$ and one of its starting points is connected to $u\in
Madarasi@19: V_{1}\}$.
Madarasi@28: 
alpar@29: If, unfortunately, the nodes of the path were the first $k$ nodes in the
alpar@29: matching order, the algorithm would iterate through all the possible $k$
Madarasi@19: long paths in $G_{2}$, and it would recognize that no path can be
Madarasi@19: extended to $G'_{1}$.
Madarasi@19: \newline
Madarasi@19: However, had it started by the matching of $G_{1}$, it would not
Madarasi@19: have matched any nodes of the path.
Madarasi@19: \end{example}
Madarasi@19: 
Madarasi@19: These examples may look artificial, but the same problems also appear
Madarasi@19: in real-world instances, even though in a less obvious way.
Madarasi@19: 
Madarasi@28: %\subsection{Preparations}
Madarasi@28: %\begin{claim}
Madarasi@28: %\label{claim:claimCoverFromLeft}
Madarasi@28: %The total ordering relation uniquely determines a node order, in which
Madarasi@28: %the nodes of $V_{1}$ will be covered by VF2. From the point of
Madarasi@28: %view of the matching procedure, this means, that always the same node
Madarasi@28: %of $G_{1}$ will be covered on the $d$-th level.
Madarasi@28: %\end{claim}
alpar@2: 
Madarasi@28: %\begin{definition}
Madarasi@28: %An order $(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{1}|)})$ of
Madarasi@28: %$V_{1}$ is \textbf{matching order} if there exists $\prec$ total
Madarasi@28: %ordering relation, s.t. the VF2 with $\prec$ on the d-th level finds
Madarasi@28: %pair for $u_{\sigma(d)}$ for all $d\in\{1,..,|V_{1}|\}$.
Madarasi@28: %\end{definition}
alpar@2: 
Madarasi@28: %\begin{claim}\label{claim:MOclaim}
Madarasi@28: %A total ordering is matching order iff the nodes of every component
Madarasi@28: %form an interval in the node sequence, and every node connects to a
Madarasi@28: %previous node in its component except the first node of each component.
Madarasi@28: %\end{claim}
alpar@2: 
Madarasi@28: %In summary, a total ordering always uniquely determines a matching
Madarasi@28: %order, and every matching order can be determined by a total ordering,
Madarasi@28: %however, more than one different total orderings may determine the
Madarasi@28: %same matching order.
alpar@2: 
Madarasi@28: \subsection{Matching order}
alpar@2: \begin{notation}
Madarasi@19: Let \textbf{F$_\mathcal{M}$(l)}$:=|\{v\in V_{2} :
Madarasi@28: l=\mathcal{L}(v)\}|-|\{u\in \mathcal{M} : l=\mathcal{L}(u)\}|$,
Madarasi@19: where $l$ is a label and $\mathcal{M}\subseteq V_{1}$.
alpar@2: \end{notation}
alpar@2: 
Madarasi@28: \begin{definition}Let $\mathbf{arg\ max}_{f}(S) :=\{u\in S : f(u)=max_{v\in S}\{f(v)\}\}$ and $\mathbf{arg\ min}_{f}(S) := arg\ max_{(-f)}(S)$, where $S$ is a finite set and $f:S\longrightarrow \mathbb{R}$.
alpar@2: \end{definition}
alpar@2: 
Madarasi@28: \begin{notation}
Madarasi@28: Let $deg(v)$ denote the degree of node $v$.
Madarasi@28: \end{notation}
Madarasi@28: 
Madarasi@28: \begin{algorithm}[H]
Madarasi@8: \algtext*{EndIf}
Madarasi@8: \algtext*{EndProcedure}
alpar@2: \algtext*{EndWhile}
Madarasi@13: \algtext*{EndFor}
alpar@2: \caption{\hspace{0.5cm}$The\ method\ of\ VF2++\ for\ determining\ the\ node\ order$}\label{alg:VF2PPPseu}
alpar@2: \begin{algorithmic}[1]
alpar@3: \Procedure{VF2++order}{} \State $\mathcal{M}$ := $\emptyset$
Madarasi@19: \Comment{matching order} \While{$V_{1}\backslash \mathcal{M}
alpar@3:   \neq\emptyset$} \State $r\in$ arg max$_{deg}$ (arg
Madarasi@19: min$_{F_\mathcal{M}\circ \mathcal{L}}(V_{1}\backslash
alpar@3: \mathcal{M})$)\label{alg:findMin} \State Compute $T$, a BFS tree with
alpar@3: root node $r$.  \For{$d=0,1,...,depth(T)$} \State $V_d$:=nodes of the
Madarasi@28: $d$-th level \State Process $V_d$ \Comment{See Algorithm~\ref{alg:VF2PPProcess1}} \EndFor
alpar@3: \EndWhile \EndProcedure
alpar@2: \end{algorithmic}
alpar@2: \end{algorithm}
alpar@2: 
alpar@2: \begin{algorithm}
Madarasi@8: \algtext*{EndIf}
Madarasi@8: \algtext*{EndProcedure}%ne nyomtasson ..
alpar@2: \algtext*{EndWhile}
Madarasi@8: \caption{\hspace{.5cm}$The\ method\ for\ processing\ a\ level\ of\ the\ BFS\ tree$}\label{alg:VF2PPProcess1}
alpar@2: \begin{algorithmic}[1]
Madarasi@17: \Procedure{VF2++ProcessLevel}{$V_{d}$} \While{$V_d\neq\emptyset$}
Madarasi@28: \State $m\in$ arg min$_{F_\mathcal{M}\circ\ \mathcal{L}}($ arg max$_{deg}($arg
alpar@3: max$_{Conn_{\mathcal{M}}}(V_{d})))$ \State $V_d:=V_d\backslash m$
alpar@3: \State Append node $m$ to the end of $\mathcal{M}$ \State Refresh
alpar@3: $F_\mathcal{M}$ \EndWhile \EndProcedure
alpar@2: \end{algorithmic}
alpar@2: \end{algorithm}
alpar@2: 
Madarasi@28: Algorithm~\ref{alg:VF2PPPseu} is a high-level description of the
alpar@4: matching order procedure of VF2++. It computes a BFS tree for each
Madarasi@19: component in ascending order of their rarest node labels and largest $deg$,
Madarasi@28: whose root vertex is the minimal node of its component. Algorithm~\ref{alg:VF2PPProcess1} is a method to process a level of the BFS tree, which appends the nodes of the current level in descending
Madarasi@8: lexicographic order by $(Conn_{\mathcal{M}},deg,-F_\mathcal{M})$ separately
Madarasi@8: to $\mathcal{M}$, and refreshes $F_\mathcal{M}$ immediately.
alpar@2: 
Madarasi@28: \begin{claim}
Madarasi@28: Algorithm~\ref{alg:VF2PPPseu} provides a matching order.
Madarasi@28: \end{claim}
alpar@2: 
alpar@2: 
alpar@2: \subsection{Cutting rules}
alpar@2: \label{VF2PPCuttingRules}
Madarasi@19: This section presents the cutting rules of VF2++, which are improved by using extra information coming from the node labels.
alpar@2: \begin{notation}
Madarasi@19: Let $\mathbf{\Gamma_{1}^{l}(u)}:=\{\tilde{u} : \mathcal{L}(\tilde{u})=l
Madarasi@19: \wedge \tilde{u}\in \Gamma_{1} (u)\}$ and
Madarasi@19: $\mathbf{\Gamma_{2}^{l}(v)}:=\{\tilde{v} : \mathcal{L}(\tilde{v})=l \wedge
Madarasi@19: \tilde{v}\in \Gamma_{2} (v)\}$, where $u\in V_{1}$, $v\in
Madarasi@19: V_{2}$ and $l$ is a label.
alpar@2: \end{notation}
alpar@2: 
Madarasi@28: \begin{claim}[Cutting function for ISO]
Madarasi@28: \[LabCut_{ISO}((u,v),\mathfrak{m}):=\bigvee_{l\ is\ label}|\Gamma_{2}^{l} (v) \cap T_{2}(\mathfrak{m})|\!\neq\!|\Gamma_{1}^{l}(u)\cap T_{1}(\mathfrak{m})|\  \vee\]\[\bigvee_{l\ is\ label} \newline |\Gamma_{2}^{l}(v)\cap \tilde{T}_{2}(\mathfrak{m})| \neq |\Gamma_{1}^{l}(u)\cap \tilde{T}_{1}(\mathfrak{m})|\] is a cutting function for ISO.
alpar@2: \end{claim}
Madarasi@13: 
Madarasi@28: \begin{claim}[Cutting function for IND]
Madarasi@28: \[LabCut_{IND}((u,v),\mathfrak{m}):=\bigvee_{l\ is\ label}|\Gamma_{2}^{l} (v) \cap T_{2}(\mathfrak{m})|\!<\!|\Gamma_{1}^{l}(u)\cap T_{1}(\mathfrak{m})|\ \vee\]\[\bigvee_{l\ is\ label} \newline |\Gamma_{2}^{l}(v)\cap \tilde{T}_{2}(\mathfrak{m})| < |\Gamma_{1}^{l}(u)\cap \tilde{T}_{1}(\mathfrak{m})|\] is a cutting function for IND.
Madarasi@28: \end{claim}
Madarasi@28: 
Madarasi@28: \begin{claim}[Cutting function for SUB]
Madarasi@28: \[LabCut_{SU\!B}((u,v),\mathfrak{m}):=\bigvee_{l\ is\ label}|\Gamma_{2}^{l} (v) \cap T_{2}(\mathfrak{m})|\!<\!|\Gamma_{1}^{l}(u)\cap T_{1}(\mathfrak{m})|\] is a cutting function for SUB.
Madarasi@19: \end{claim}
alpar@2: 
Madarasi@19: 
Madarasi@19: 
Madarasi@22: \section{Implementation details}\label{sec:VF2ppImpl}
alpar@3: This section provides a detailed summary of an efficient
alpar@3: implementation of VF2++.
Madarasi@28: \begin{notation}
Madarasi@28: Let $\Delta_1$ and $\Delta_2$ denote the largest degree in $G_1$ and $G_2$, respectively, and let $\Delta=\max\{\Delta_1,\Delta_2\}$.
Madarasi@28: \end{notation}
Madarasi@22: \subsection{Storing a mapping}
alpar@3: After fixing an arbitrary node order ($u_0, u_1, ..,
Madarasi@28: u_{|V_{1}|-1}$) of $G_{1}$, an array $M$ can be used to store
alpar@3: the current mapping in the following way.
alpar@2: \[
alpar@3:  M[i] =
alpar@2:   \begin{cases} 
Madarasi@19:    v & if\ (u_i,v)\ is\ in\ the\ mapping\\ INV\!ALI\!D &
Madarasi@17:    if\ no\ node\ has\ been\ mapped\ to\ u_i,
alpar@2:   \end{cases}
alpar@2: \]
Madarasi@28: where $i\in\{0,1, ..,|V_{1}|-1\}$, $v\in V_{2}$ and $INV\!ALI\!D$
alpar@3: means "no node".
Madarasi@22: \subsection{Avoiding the recurrence}
alpar@4: The recursion of Algorithm~\ref{alg:VF2Pseu} can be realized
Madarasi@9: as a \textit{while loop}, which has a loop counter $depth$ denoting the
Madarasi@28: current depth of the recursion. Fixing a matching order, let $M$
Madarasi@28: denote the array storing the current mapping. Observe that
Madarasi@19: $M$ is $INV\!ALI\!D$ from index $depth$+1 and not $INV\!ALI\!D$ before
Madarasi@9: $depth$. $M[depth]$ changes
alpar@3: while the state is being processed, but the property is held before
alpar@3: both stepping back to a predecessor state and exploring a successor
alpar@3: state.
alpar@2: 
alpar@29: The necessary part of the candidate set is easy to maintain or
alpar@29: compute by following
Madarasi@28: the steps described in Section~\ref{candidateComputingVF2}. A much faster method
Madarasi@28: has been designed for biological and sparse graphs, see the next
alpar@3: section for details.
alpar@2: 
Madarasi@22: \subsection{Calculating the candidates for a node}
Madarasi@28: The task is not to maintain the candidate set, but to generate the
Madarasi@19: candidate nodes in $G_{2}$ for a given node $u\in V_{1}$.  In
Madarasi@20: case of any of the three problem types and a mapping $\mathfrak{m}$, if a node $v\in
Madarasi@19: V_{2}$ is a potential pair of $u\in V_{1}$, then $\forall
Madarasi@20: u'\in \mathfrak{D}(\mathfrak{m}) : (u,u')\in
Madarasi@20: E_{1}\Rightarrow (v,\mathfrak{m}(u'))\in
alpar@29: E_{2}$. That is, each covered neighbor of $u$ has to be mapped to
alpar@29: a covered neighbor of $v$, i.e. selecting arbitrarily a covered neighbor $u'$ of $u$, all of the admissible candidates for $u$ are among the neighbors of $\mathfrak{m}(u')$.
alpar@2: 
Madarasi@28: Having said that, an algorithm running in $\Theta(\Delta_2)$ time is
alpar@3: describable if there exists a covered node in the component containing
Madarasi@17: $u$, and a linear one otherwise.
alpar@2: 
alpar@2: 
Madarasi@22: \subsection{Determining the node order}
alpar@3: This section describes how the node order preprocessing method of
alpar@3: VF2++ can efficiently be implemented.
alpar@2: 
alpar@3: For using lookup tables, the node labels are associated with the
alpar@3: numbers $\{0,1,..,|K|-1\}$, where $K$ is the set of the labels. It
Madarasi@9: enables $F_\mathcal{M}$ to be stored in an array. At first, the node order
alpar@3: $\mathcal{M}=\emptyset$, so $F_\mathcal{M}[i]$ is the number of nodes
Madarasi@28: in $V_{2}$ having label $i$, which is easy to compute in
Madarasi@28: $\Theta(|V_{2}|)$ steps.
alpar@2: 
Madarasi@19: Representing $\mathcal{M}\subseteq V_{1}$ as an array of
Madarasi@28: size $|V_{1}|$, both the computation of the BFS tree, and processing its levels by Algorithm~\ref{alg:VF2PPProcess1} can be done in-place by swapping nodes.
alpar@2: 
Madarasi@22: \subsection{Cutting rules}
alpar@29: Section~\ref{VF2PPCuttingRules} described the cutting rules
alpar@29: using the sets $T_{1}$, $T_{2}$, $\tilde T_{1}$
alpar@29: and $\tilde T_{2}$, which are dependent on the current mapping. The aim is to check the labeled cutting
Madarasi@28: rules of VF2++ in $\Theta(\Delta)$ time.
alpar@2: 
alpar@29: Firstly, suppose that these four sets are given a way, that
alpar@3: checking whether a node is in a certain set takes constant time,
alpar@3: e.g. they are given by their 0-1 characteristic vectors. Let $L$ be an
alpar@3: initially zero integer lookup table of size $|K|$. After incrementing
Madarasi@19: $L[\mathcal{L}(u')]$ for all $u'\in \Gamma_{1}(u) \cap T_{1}(\mathfrak{m})$ and
Madarasi@19: decrementing $L[\mathcal{L}(v')]$ for all $v'\in\Gamma_{2} (v) \cap
alpar@29: T_{2}(\mathfrak{m})$, the first part of the cutting rules can be checked in
Madarasi@28: $\Theta(\Delta)$ time by considering the proper signs of $L$. Setting $L$
Madarasi@28: to zero takes $\Theta(\Delta)$ time again, which makes it possible to use
Madarasi@9: the same table through the whole algorithm. The second part of the
alpar@3: cutting rules can be verified using the same method with $\tilde
Madarasi@19: T_{1}$ and $\tilde T_{2}$ instead of $T_{1}$ and
Madarasi@28: $T_{2}$. Thus, the overall time complexity is $\Theta(\Delta)$.
alpar@2: 
Madarasi@28: To maintain the sets $T_{1}$, $T_{2}$, $\tilde T_{1}$
Madarasi@28: and $\tilde T_{2}$, two other integer lookup tables storing the number of covered neighbours of the nodes of the two graphs can be used. This representation allows constant-time membership checking, furthermore it is maintainable in $\Theta(\Delta)$ time whenever a node pair is added or subtracted by incrementing
alpar@3: or decrementing the proper indices. A further improvement is that the
Madarasi@19: values of $L[\mathcal{L}(u')]$ in case of checking $u$ are dependent only on
Madarasi@28: $u$, i.e. on the current depth of the recursion, so for each $u\in V_{1}$, an array of pairs \textit{(label, number of such labels)} can store $L$. Note that these arrays are at most of size
Madarasi@28: $\Delta_1$ if pairs with non-appearing node labels are discarded.
alpar@2: 
Madarasi@19: Using similar techniques, the consistency function can be evaluated in
Madarasi@28: $\Theta(\Delta)$ steps, as well.
alpar@2: 
Madarasi@22: \section{Experimental results}\label{sec:ExpRes}
Madarasi@28: This section compares the performance of VF2++ and VF2~Plus. According to
Madarasi@19: our experience, both algorithms run faster than VF2 with orders of
Madarasi@19: magnitude, thus its inclusion was not reasonable.
alpar@2: 
alpar@29: The algorithms were implemented in C++ using the open-source LEMON
alpar@29: graph and network optimization
alpar@29: library~\cite{LEMON}\cite{o11:_lemon_open_sourc_c_graph_templ_librar}. The
alpar@29: tests were carried out on a Linux-based system with an Intel i7 X980
alpar@29: 3.33 GHz CPU and 6 GB of RAM.
alpar@29: 
alpar@2: \subsection{Biological graphs}
alpar@3: The tests have been executed on a recent biological dataset created
alpar@3: for the International Contest on Pattern Search in Biological
Madarasi@28: Databases~\cite{Content}, which has been constructed of molecule,
Madarasi@7: protein and contact map graphs extracted from the Protein Data
Madarasi@28: Bank~\cite{ProteinDataBank}.
alpar@2: 
alpar@3: The molecule dataset contains small graphs with less than 100 nodes
alpar@3: and an average degree of less than 3. The protein dataset contains
alpar@3: graphs having 500-10 000 nodes and an average degree of 4, while the
alpar@3: contact map dataset contains graphs with 150-800 nodes and an average
alpar@3: degree of 20.  \\
alpar@2: 
Madarasi@28: In the following, both the induced subgraph and the graph
Madarasi@28: isomorphism problems will be examined.
alpar@29: This dataset provides graph pairs, between which all the induced subgraph isomorphisms have to be found. For the running times, please see Figure~\ref{fig:bioIND}.
Madarasi@7: 
Madarasi@7: In an other experiment, the nodes of each graph in the database had been
Madarasi@7: shuffled, and an isomorphism between the shuffled and the original
Madarasi@28: graph was searched. The running times are shown on Figure~\ref{fig:bioISO}.
Madarasi@7: 
Madarasi@7: 
Madarasi@17: \begin{figure}[H]
Madarasi@17: \vspace*{-2cm}
Madarasi@17: \hspace*{-1.5cm}
Madarasi@17: \begin{subfigure}[b]{0.55\textwidth}
Madarasi@17: \begin{figure}[H]
Madarasi@17: \begin{tikzpicture}[trim axis left, trim axis right]
Madarasi@28: \begin{axis}[title=Molecules IND,xlabel={$|V_2|$},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
Madarasi@17: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
Madarasi@17:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
Madarasi@17: %\addplot+[only marks] table {proteinsOrig.txt};
Madarasi@17: \addplot table {Orig/Molecules.32.txt}; \addplot[mark=triangle*,mark
Madarasi@17:   size=1.8pt,color=red] table {VF2PPLabel/Molecules.32.txt};
Madarasi@17: \end{axis}
Madarasi@17: \end{tikzpicture}
Madarasi@17: \caption{In the case of molecules, the algorithms have
Madarasi@17:   similar behaviour, but VF2++ is almost two times faster even on such
Madarasi@17:   small graphs.} \label{fig:INDMolecule}
Madarasi@17: \end{figure}
Madarasi@17: \end{subfigure}
Madarasi@17: \hspace*{1.5cm}
Madarasi@17: \begin{subfigure}[b]{0.55\textwidth}
Madarasi@17: \begin{figure}[H]
Madarasi@17: \begin{tikzpicture}[trim axis left, trim axis right]
Madarasi@28: \begin{axis}[title=Contact maps IND,xlabel={$|V_2|$},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
Madarasi@17: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
Madarasi@17:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
Madarasi@17: %\addplot+[only marks] table {proteinsOrig.txt};
Madarasi@17: \addplot table {Orig/ContactMaps.128.txt};
Madarasi@17: \addplot[mark=triangle*,mark size=1.8pt,color=red] table
Madarasi@17:         {VF2PPLabel/ContactMaps.128.txt};
Madarasi@17: \end{axis}
Madarasi@17: \end{tikzpicture}
Madarasi@17: \caption{On contact maps, VF2++ runs almost in constant time, while VF2
alpar@29:   Plus has a near-linear behavior.} \label{fig:INDContact}
Madarasi@17: \end{figure}
Madarasi@17: \end{subfigure}
Madarasi@17: 
Madarasi@17: \begin{center}
Madarasi@17: \vspace*{-0.5cm}
Madarasi@17: \begin{subfigure}[b]{0.55\textwidth}
Madarasi@17: \begin{figure}[H]
Madarasi@17: \begin{tikzpicture}[trim axis left, trim axis right]
Madarasi@28:   \begin{axis}[title=Proteins IND,xlabel={$|V_2|$},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
Madarasi@17:   =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
Madarasi@17:     west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}] %\addplot+[only marks] table
Madarasi@17:     {proteinsOrig.txt}; \addplot[mark=*,mark size=1.2pt,color=blue]
Madarasi@17:     table {Orig/Proteins.256.txt}; \addplot[mark=triangle*,mark
Madarasi@17:       size=1.8pt,color=red] table {VF2PPLabel/Proteins.256.txt};
Madarasi@17:   \end{axis}
Madarasi@17:   \end{tikzpicture}
Madarasi@28: \caption{Both of the algorithms have linear behaviour on protein
Madarasi@17:   graphs. VF2++ is more than 10 times faster than VF2
Madarasi@17:   Plus.} \label{fig:INDProt}
Madarasi@17: \end{figure}
Madarasi@17: \end{subfigure}
Madarasi@17: \end{center}
Madarasi@17: \vspace*{-0.5cm}
Madarasi@28: \caption{\normalsize{Induced subgraph isomorphism problem on biological graphs}}\label{fig:bioIND}
Madarasi@17: \end{figure}
Madarasi@17: 
alpar@2: 
alpar@2: \begin{figure}[H]
Madarasi@7: \vspace*{-2cm}
Madarasi@7: \hspace*{-1.5cm}
Madarasi@7: \begin{subfigure}[b]{0.55\textwidth}
Madarasi@7: \begin{figure}[H]
Madarasi@7: \begin{tikzpicture}[trim axis left, trim axis right]
Madarasi@28: \begin{axis}[title=Molecules ISO,xlabel={$|V_2|$},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
Madarasi@7: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
Madarasi@7:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
Madarasi@7: %\addplot+[only marks] table {proteinsOrig.txt};
Madarasi@7: \addplot table {Orig/moleculesIso.txt}; \addplot[mark=triangle*,mark
Madarasi@7:   size=1.8pt,color=red] table {VF2PPLabel/moleculesIso.txt};
Madarasi@7: \end{axis}
Madarasi@7: \end{tikzpicture}
Madarasi@28: \caption{The results are close to each other on contact maps, but VF2++ seems to be slightly faster as the number of nodes increases.
Madarasi@28:   }\label{fig:ISOMolecule}
Madarasi@7: \end{figure}
Madarasi@7: \end{subfigure}
Madarasi@7: \hspace*{1.5cm}
Madarasi@7: \begin{subfigure}[b]{0.55\textwidth}
Madarasi@7: \begin{figure}[H]
Madarasi@7: \begin{tikzpicture}[trim axis left, trim axis right]
Madarasi@28: \begin{axis}[title=Contact maps ISO,xlabel={$|V_2|$},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
Madarasi@7: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
Madarasi@7:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
Madarasi@7: %\addplot+[only marks] table {proteinsOrig.txt};
Madarasi@7: \addplot table {Orig/contactMapsIso.txt}; \addplot[mark=triangle*,mark
Madarasi@7:   size=1.8pt,color=red] table {VF2PPLabel/contactMapsIso.txt};
Madarasi@7: \end{axis}
Madarasi@7: \end{tikzpicture}
Madarasi@28: \caption{In the case of molecules, there is no significant
Madarasi@28:   difference, but VF2++ performs consistently better.}\label{fig:ISOContact}
Madarasi@7: \end{figure}
Madarasi@7: \end{subfigure}
Madarasi@7: 
alpar@2: \begin{center}
Madarasi@7: \vspace*{-0.5cm}
Madarasi@7: \begin{subfigure}[b]{0.55\textwidth}
Madarasi@7: \begin{figure}[H]
Madarasi@7: \begin{tikzpicture}[trim axis left, trim axis right]
Madarasi@28: \begin{axis}[title=Proteins ISO,xlabel={$|V_2|$},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
Madarasi@7: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
Madarasi@7:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
Madarasi@7: %\addplot+[only marks] table {proteinsOrig.txt};
Madarasi@7: \addplot table {Orig/proteinsIso.txt}; \addplot[mark=triangle*,mark
Madarasi@7:   size=1.8pt,color=red] table {VF2PPLabel/proteinsIso.txt};
Madarasi@7: \end{axis}
Madarasi@7: \end{tikzpicture}
Madarasi@28: \caption{On protein graphs, VF2~Plus has a super linear time
Madarasi@7:   complexity, while VF2++ runs in near constant time. The difference
Madarasi@28:   is about two orders of magnitude on large graphs.}\label{fig:ISOProt}
Madarasi@7: \end{figure}
Madarasi@7: \end{subfigure}
Madarasi@7: \end{center}
Madarasi@7: \vspace*{-0.6cm}
Madarasi@28: \caption{\normalsize{Graph isomorphism problem on biological graphs}}\label{fig:bioISO}
Madarasi@7: \end{figure}
Madarasi@7: 
Madarasi@7: 
alpar@2: 
alpar@2: 
alpar@2: \subsection{Random graphs}
Madarasi@28: This section compares VF2++ with VF2~Plus on random graphs of large
alpar@3: size. The node labels are uniformly distributed.  Let $\delta$ denote
alpar@3: the average degree.  For the parameters of problems solved in the
alpar@3: experiments, please see the top of each chart.
Madarasi@28: \subsubsection{Graph isomorphism problem}
alpar@3: To evaluate the efficiency of the algorithms in the case of graph
Madarasi@28: isomorphism problem, random connected graphs of less than 20 000 nodes have been
alpar@3: considered. Generating a random graph and shuffling its nodes, an
alpar@29: isomorphism had to be found. Figure~\ref{fig:randISO} shows the running times
alpar@4: on graph sets of various density.
alpar@2: 
Madarasi@7: 
Madarasi@7: 
Madarasi@7: 
Madarasi@12: \begin{figure}
Madarasi@7: \vspace*{-1.5cm}
Madarasi@7: \hspace*{-1.5cm}
Madarasi@7: \begin{subfigure}[b]{0.55\textwidth}
alpar@2: \begin{center}
alpar@2: \begin{tikzpicture}
Madarasi@28: \begin{axis}[title={Random ISO, $\delta = 5$},width=7.2cm,height=6cm,xlabel={$|V_2|$},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
alpar@3: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
alpar@3:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
alpar@2: %\addplot+[only marks] table {proteinsOrig.txt};
alpar@2: \addplot table {randGraph/iso/vf2pIso5_1.txt};
alpar@3: \addplot[mark=triangle*,mark size=1.8pt,color=red] table
alpar@3:         {randGraph/iso/vf2ppIso5_1.txt};
alpar@2: \end{axis}
alpar@2: \end{tikzpicture}
alpar@2: \end{center}
Madarasi@7: \end{subfigure}
Madarasi@7: %\hspace{1cm}
Madarasi@7: \begin{subfigure}[b]{0.55\textwidth}
alpar@2: \begin{center}
alpar@2: \begin{tikzpicture}
Madarasi@28: \begin{axis}[title={Random ISO, $\delta = 10$},width=7.2cm,height=6cm,xlabel={$|V_2|$},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
alpar@3: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
alpar@3:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
alpar@2: %\addplot+[only marks] table {proteinsOrig.txt};
alpar@2: \addplot table {randGraph/iso/vf2pIso10_1.txt};
alpar@3: \addplot[mark=triangle*,mark size=1.8pt,color=red] table
alpar@3:         {randGraph/iso/vf2ppIso10_1.txt};
alpar@2: \end{axis}
alpar@2: \end{tikzpicture}
alpar@2: \end{center}
Madarasi@7: \end{subfigure}
Madarasi@7: %%\hspace{1cm}
Madarasi@7: \hspace*{-1.5cm}
Madarasi@7: \begin{subfigure}[b]{0.55\textwidth}
alpar@2: \begin{center}
alpar@2: \begin{tikzpicture}
Madarasi@28: \begin{axis}[title={Random ISO, $\delta = 15$},width=7.2cm,height=6cm,xlabel={$|V_2|$},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
alpar@3: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
alpar@3:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
alpar@2: %\addplot+[only marks] table {proteinsOrig.txt};
alpar@2: \addplot table {randGraph/iso/vf2pIso15_1.txt};
alpar@3: \addplot[mark=triangle*,mark size=1.8pt,color=red] table
alpar@3:         {randGraph/iso/vf2ppIso15_1.txt};
alpar@2: \end{axis}
alpar@2: \end{tikzpicture}
alpar@2: \end{center}
Madarasi@7:      \end{subfigure}
Madarasi@7:      \begin{subfigure}[b]{0.55\textwidth}
alpar@2: \begin{center}
alpar@2: \begin{tikzpicture}
Madarasi@28: \begin{axis}[title={Random ISO, $\delta = 100$},width=7.2cm,height=6cm,xlabel={$|V_2|$},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
alpar@3: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
alpar@3:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
alpar@2: %\addplot+[only marks] table {proteinsOrig.txt};
alpar@2: \addplot table {randGraph/iso/vf2pIso100_1.txt};
alpar@3: \addplot[mark=triangle*,mark size=1.8pt,color=red] table
alpar@3:         {randGraph/iso/vf2ppIso100_1.txt};
alpar@2: \end{axis}
alpar@2: \end{tikzpicture}
Madarasi@23: \end{center}
Madarasi@7: \end{subfigure}
alpar@2: \vspace*{-0.8cm}
Madarasi@28: \caption{Graph isomorphism problem on random graphs
Madarasi@23: }\label{fig:randISO}
alpar@2: \end{figure}
alpar@2: 
alpar@2: 
Madarasi@28: \subsubsection{Induced subgraph isomorphism problem}
Madarasi@28: This section presents a comparison of VF2++ and VF2~Plus in the case
Madarasi@28: of induced subgraph isomorphism problem. In addition to the size of graph $G_2$, that of $G_1$ dramatically influences the hardness of
Madarasi@28: a given problem too, so the overall picture is provided by examining graphs to be embedded of various size.
alpar@2: 
Madarasi@17: For each chart, a number $0<\rho< 1$ has been fixed, and the following
Madarasi@19: has been executed 150 times. Generating a large graph $G_{2}$ of an average degree of $\delta$,
Madarasi@28: choose 10 of its induced subgraphs having $\rho|V_{2}|$ nodes,
Madarasi@28: and for all the 10 subgraphs find a mapping by using both graph
alpar@3: matching algorithms.  The $\delta = 5, 10, 35$ and $\rho = 0.05, 0.1,
Madarasi@23: 0.3, 0.8$ cases have been examined, see
Madarasi@28: Figure~\ref{fig:randIND5},~\ref{fig:randIND10}~and~\ref{fig:randIND35}.
alpar@2: 
alpar@2: 
alpar@2: 
alpar@2: 
alpar@2: 
Madarasi@12: \begin{figure}
Madarasi@7: \vspace*{-1.5cm}
Madarasi@7: \hspace*{-1.5cm}
alpar@2: \begin{subfigure}[b]{0.55\textwidth}
alpar@2: \begin{center}
alpar@2: \begin{tikzpicture}
Madarasi@28: \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.05$},width=7.2cm,height=6cm,xlabel={$|V_2|$},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
alpar@3: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
alpar@3:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
alpar@2: %\addplot+[only marks] table {proteinsOrig.txt};
alpar@2: \addplot table {randGraph/ind/vf2pInd5_0.05.txt};
alpar@3: \addplot[mark=triangle*,mark size=1.8pt,color=red] table
alpar@3:         {randGraph/ind/vf2ppInd5_0.05.txt};
alpar@2: \end{axis}
alpar@2: \end{tikzpicture}
alpar@2: \end{center}
alpar@2:      \end{subfigure}
alpar@2:      \begin{subfigure}[b]{0.55\textwidth}
alpar@2: \begin{center}
alpar@2: \begin{tikzpicture}
Madarasi@28: \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.1$},width=7.2cm,height=6cm,xlabel={$|V_2|$},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
alpar@3: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
alpar@3:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
alpar@2: %\addplot+[only marks] table {proteinsOrig.txt};
alpar@2: \addplot table {randGraph/ind/vf2pInd5_0.1.txt};
alpar@3: \addplot[mark=triangle*,mark size=1.8pt,color=red] table
alpar@3:         {randGraph/ind/vf2ppInd5_0.1.txt};
alpar@2: \end{axis}
alpar@2: \end{tikzpicture}
alpar@2: \end{center}
alpar@2: \end{subfigure}
Madarasi@7: \hspace*{-1.5cm}
alpar@2: \begin{subfigure}[b]{0.55\textwidth}
alpar@2: \begin{center}
alpar@2: \begin{tikzpicture}
Madarasi@28: \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.3$},width=7.2cm,height=6cm,xlabel={$|V_2|$},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
alpar@3: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
alpar@3:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
alpar@2: %\addplot+[only marks] table {proteinsOrig.txt};
alpar@2: \addplot table {randGraph/ind/vf2pInd5_0.3.txt};
alpar@3: \addplot[mark=triangle*,mark size=1.8pt,color=red] table
alpar@3:         {randGraph/ind/vf2ppInd5_0.3.txt};
alpar@2: \end{axis}
alpar@2: \end{tikzpicture}
alpar@2: \end{center}
alpar@2:      \end{subfigure}
alpar@2:      \begin{subfigure}[b]{0.55\textwidth}
alpar@2: \begin{center}
alpar@2: \begin{tikzpicture}
Madarasi@28: \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={$|V_2|$},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
alpar@3: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
alpar@3:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
alpar@2: %\addplot+[only marks] table {proteinsOrig.txt};
alpar@2: \addplot table {randGraph/ind/vf2pInd5_0.8.txt};
alpar@3: \addplot[mark=triangle*,mark size=1.8pt,color=red] table
alpar@3:         {randGraph/ind/vf2ppInd5_0.8.txt};
alpar@2: \end{axis}
alpar@2: \end{tikzpicture}
Madarasi@23: \end{center}
alpar@2: \end{subfigure}
alpar@2: \vspace*{-0.8cm}
Madarasi@28: \caption{Induced subgraph isomorphism problem on random graphs having an average degree of
Madarasi@28:   5}\label{fig:randIND5}
alpar@2: \end{figure}
alpar@2: 
alpar@2: 
Madarasi@23: \begin{figure}
Madarasi@7: \vspace*{-1.5cm}
Madarasi@7: \hspace*{-1.5cm}
alpar@2: \begin{subfigure}[b]{0.55\textwidth}
alpar@2: \begin{center}
Madarasi@7: \hspace*{-0.5cm}
alpar@2: \begin{tikzpicture}
Madarasi@28: \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.05$},width=7.2cm,height=6cm,xlabel={$|V_2|$},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
alpar@3: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
alpar@3:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
alpar@2: %\addplot+[only marks] table {proteinsOrig.txt};
alpar@2: \addplot table {randGraph/ind/vf2pInd10_0.05.txt};
alpar@3: \addplot[mark=triangle*,mark size=1.8pt,color=red] table
alpar@3:         {randGraph/ind/vf2ppInd10_0.05.txt};
alpar@2: \end{axis}
alpar@2: \end{tikzpicture}
alpar@2: \end{center}
alpar@2:      \end{subfigure}
alpar@2:      \begin{subfigure}[b]{0.55\textwidth}
alpar@2: \begin{center}
Madarasi@7:      \hspace*{-0.5cm}
alpar@2: \begin{tikzpicture}
Madarasi@28: \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.1$},width=7.2cm,height=6cm,xlabel={$|V_2|$},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
alpar@3: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
alpar@3:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
alpar@2: %\addplot+[only marks] table {proteinsOrig.txt};
alpar@2: \addplot table {randGraph/ind/vf2pInd10_0.1.txt};
alpar@3: \addplot[mark=triangle*,mark size=1.8pt,color=red] table
alpar@3:         {randGraph/ind/vf2ppInd10_0.1.txt};
alpar@2: \end{axis}
alpar@2: \end{tikzpicture}
alpar@2: \end{center}
alpar@2: \end{subfigure}
Madarasi@7: \hspace*{-1.5cm}
alpar@2: \begin{subfigure}[b]{0.55\textwidth}
alpar@2: \begin{center}
alpar@2: \begin{tikzpicture}
Madarasi@28: \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.3$},width=7.2cm,height=6cm,xlabel={$|V_2|$},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
alpar@3: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
alpar@3:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
alpar@2: %\addplot+[only marks] table {proteinsOrig.txt};
alpar@2: \addplot table {randGraph/ind/vf2pInd10_0.3.txt};
alpar@3: \addplot[mark=triangle*,mark size=1.8pt,color=red] table
alpar@3:         {randGraph/ind/vf2ppInd10_0.3.txt};
alpar@2: \end{axis}
alpar@2: \end{tikzpicture}
alpar@2: \end{center}
alpar@2:      \end{subfigure}
alpar@2:      \begin{subfigure}[b]{0.55\textwidth}
alpar@2: \begin{center}
alpar@2: \begin{tikzpicture}
Madarasi@28: \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={$|V_2|$},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
alpar@3: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
alpar@3:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
alpar@2: %\addplot+[only marks] table {proteinsOrig.txt};
alpar@2: \addplot table {randGraph/ind/vf2pInd10_0.8.txt};
alpar@3: \addplot[mark=triangle*,mark size=1.8pt,color=red] table
alpar@3:         {randGraph/ind/vf2ppInd10_0.8.txt};
alpar@2: \end{axis}
alpar@2: \end{tikzpicture}
Madarasi@23: \end{center}
alpar@2: \end{subfigure}
alpar@2: \vspace*{-0.8cm}
Madarasi@28: \caption{Induced subgraph isomorphism problem on random graphs having an average degree of
Madarasi@28:   10}\label{fig:randIND10}
alpar@2: \end{figure}
alpar@2: 
alpar@2: 
alpar@2: 
Madarasi@23: \begin{figure}
Madarasi@7: \vspace*{-1.5cm}
Madarasi@7: \hspace*{-1.5cm}
alpar@2: \begin{subfigure}[b]{0.55\textwidth}
alpar@2: \begin{center}
alpar@2: \begin{tikzpicture}
Madarasi@28: \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.05$},width=7.2cm,height=6cm,xlabel={$|V_2|$},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
alpar@3: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
alpar@3:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
alpar@2: %\addplot+[only marks] table {proteinsOrig.txt};
alpar@2: \addplot table {randGraph/ind/vf2pInd35_0.05.txt};
alpar@3: \addplot[mark=triangle*,mark size=1.8pt,color=red] table
alpar@3:         {randGraph/ind/vf2ppInd35_0.05.txt};
alpar@2: \end{axis}
alpar@2: \end{tikzpicture}
alpar@2: \end{center}
alpar@2:      \end{subfigure}
alpar@2:      \begin{subfigure}[b]{0.55\textwidth}
alpar@2: \begin{center}
alpar@2: \begin{tikzpicture}
Madarasi@28: \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.1$},width=7.2cm,height=6cm,xlabel={$|V_2|$},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
alpar@3: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
alpar@3:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
alpar@2: %\addplot+[only marks] table {proteinsOrig.txt};
alpar@2: \addplot table {randGraph/ind/vf2pInd35_0.1.txt};
alpar@3: \addplot[mark=triangle*,mark size=1.8pt,color=red] table
alpar@3:         {randGraph/ind/vf2ppInd35_0.1.txt};
alpar@2: \end{axis}
alpar@2: \end{tikzpicture}
alpar@2: \end{center}
alpar@2: \end{subfigure}
Madarasi@7: \hspace*{-1.5cm}
alpar@2: \begin{subfigure}[b]{0.55\textwidth}
alpar@2: \begin{center}
alpar@2: \begin{tikzpicture}
Madarasi@28: \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.3$},width=7.2cm,height=6cm,xlabel={$|V_2|$},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
alpar@3: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
alpar@3:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
alpar@2: %\addplot+[only marks] table {proteinsOrig.txt};
alpar@2: \addplot table {randGraph/ind/vf2pInd35_0.3.txt};
alpar@3: \addplot[mark=triangle*,mark size=1.8pt,color=red] table
alpar@3:         {randGraph/ind/vf2ppInd35_0.3.txt};
alpar@2: \end{axis}
alpar@2: \end{tikzpicture}
alpar@2: \end{center}
alpar@2:      \end{subfigure}
alpar@2:      \begin{subfigure}[b]{0.55\textwidth}
alpar@2: \begin{center}
alpar@2: \begin{tikzpicture}
Madarasi@28: \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={$|V_2|$},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
alpar@3: =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
alpar@3:   west},scaled x ticks = false,x tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em},y tick label style={/pgf/number
Madarasi@28:   format/1000 sep = \kern 0.08em}]
alpar@2: %\addplot+[only marks] table {proteinsOrig.txt};
alpar@2: \addplot table {randGraph/ind/vf2pInd35_0.8.txt};
alpar@3: \addplot[mark=triangle*,mark size=1.8pt,color=red] table
alpar@3:         {randGraph/ind/vf2ppInd35_0.8.txt};
alpar@2: \end{axis}
alpar@2: \end{tikzpicture}
Madarasi@23: \end{center}
alpar@2: \end{subfigure}
alpar@2: \vspace*{-0.8cm}
Madarasi@28: \caption{Induced subgraph isomorphism problem on random graphs having an average degree of
Madarasi@28:   35}\label{fig:randIND35}
alpar@2: \end{figure}
alpar@2: 
alpar@2: 
alpar@29: As the experiments above demonstrates, VF2++ is faster than VF2~Plus and able to
alpar@3: handle really large graphs in milliseconds. Note that when $IND$ was
Madarasi@28: considered and the graph to be embedded had proportionally few nodes ($\rho =
Madarasi@28: 0.05$, or $\rho = 0.1$), then VF2~Plus produced some inefficient node
alpar@4: orders (e.g. see the $\delta=10$ case on
Madarasi@17: Figure~\ref{fig:randIND10}). If these instances had been excluded, the
Madarasi@28: charts would have looked similarly to the other ones.
alpar@3: Unsurprisingly, as denser graphs are considered, both VF2++ and VF2
alpar@29: Plus slow down slightly, but remain practically usable even on graphs
alpar@3: having 10 000 nodes.
alpar@2: 
alpar@2: 
alpar@2: 
alpar@2: 
alpar@3: 
alpar@2: \section{Conclusion}
alpar@29: This paper presented VF2++, a new graph matching algorithm based on VF2, and analyzed it from a practical point of view.
alpar@2: 
alpar@3: Recognizing the importance of the node order and determining an
alpar@3: efficient one, VF2++ is able to match graphs of thousands of nodes in
alpar@3: near practically linear time including preprocessing. In addition to
Madarasi@28: the proper order, VF2++ uses more efficient cutting
alpar@29: rules, which are easy to compute and make the algorithm able to prune
alpar@3: most of the unfruitful branches without going astray.
alpar@2: 
alpar@3: In order to show the efficiency of the new method, it has been
Madarasi@28: compared to VF2~Plus~\cite{VF2Plus}, which is the best contemporary algorithm.
alpar@2: 
Madarasi@28: The experiments show that VF2++ consistently outperforms VF2~Plus on
alpar@3: biological graphs. It seems to be asymptotically faster on protein and
Madarasi@28: on contact map graphs in the case of induced subgraph isomorphism problem,
Madarasi@28: while in the case of graph isomorphism problem, it has definitely better
alpar@29: asymptotic behavior on protein graphs.
alpar@2: 
alpar@3: Regarding random sparse graphs, not only has VF2++ proved itself to be
alpar@29: faster than VF2~Plus, but it also has a practically linear behavior both
Madarasi@28: in the case of induced subgraph and graph isomorphism problems.
alpar@2: 
alpar@25: %%%%%%%%%%%%%%%%
alpar@25: \section*{Acknowledgement} \label{sec:ack}
alpar@25: %%%%%%%%%%%%%%%%
alpar@25: This research project was initiated and sponsored by QuantumBio
Madarasi@28: Inc.~\cite{QUANTUMBIO}.
alpar@25: 
alpar@25: The authors were supported by the Hungarian Scientific Research Fund -
alpar@25: OTKA, K109240 and by the J\'anos Bolyai Research Fellowship program of
alpar@25: the Hungarian Academy of Sciences.
alpar@2: 
alpar@0: 
alpar@0: %% The Appendices part is started with the command \appendix;
alpar@0: %% appendix sections are then done as normal sections
alpar@0: %% \appendix
alpar@0: 
alpar@0: %% \section{}
alpar@0: %% \label{}
alpar@0: 
alpar@0: %% If you have bibdatabase file and want bibtex to generate the
alpar@0: %% bibitems, please use
alpar@0: %%
alpar@3: \bibliographystyle{elsarticle-num} \bibliography{bibliography}
alpar@0: 
alpar@0: %% else use the following coding to input the bibitems directly in the
alpar@0: %% TeX file.
alpar@0: 
alpar@2: %% \begin{thebibliography}{00}
alpar@0: 
alpar@2: %% %% \bibitem{label}
alpar@2: %% %% Text of bibliographic item
alpar@0: 
alpar@2: %% \bibitem{}
alpar@0: 
alpar@2: %% \end{thebibliography}
alpar@2: 
alpar@0: \end{document}
alpar@0: \endinput
alpar@0: %%
alpar@0: %% End of file `elsarticle-template-num.tex'.
alpar@29: 
alpar@29: %%  LocalWords:  Subgraph Isomorphism datasets subgraphs subgraph FPT
alpar@29: %%  LocalWords:  isomorphism hypergraph Ullmann Nauty precompute BFS
alpar@29: %%  LocalWords:  bijection isomorphisms undirected infeasible dataset
alpar@29: %%  LocalWords:  preprocessing incrementing decrementing neighbours
alpar@29: %%  LocalWords:  expectable bioinformatics