# HG changeset patch
# User Madarasi Peter
# Date 1480114051 -3600
# Node ID 196396ea94b519f2990cd1ad7807e67b86771fee
# Parent  b45bac51110897e7d8593f596ccf88ae35f284f0
Vf2's consistency and cutting rules part shortened

diff -r b45bac511108 -r 196396ea94b5 damecco.tex
--- a/damecco.tex	Thu Nov 24 22:09:36 2016 +0100
+++ b/damecco.tex	Fri Nov 25 23:47:31 2016 +0100
@@ -570,22 +570,21 @@
 \]
 
 \subsection{Consistency}
-This section defines the consistency functions for the different
-problem types mentioned in Section~\ref{sec:CommProb}.
+Suppose $p=(u,v)$, where $u\in V_{small}$ and $v\in V_{large}$, $s$ is
+a state of the matching procedure, $M(s)$ is consistent mapping by
+$PT$ and $lab(u)=lab(v)$.  $Cons_{PT}(p,M(s))$ checks whether
+including pair $p$ into $M(s)$ leads to a consistent mapping by $PT$.
+
+For example, the consistency function of induced subgraph isomorphism is as follows.
 \begin{notation}
 Let $\mathbf{\Gamma_{small} (u)}:=\{\tilde{u}\in V_{small} :
 (u,\tilde{u})\in E_{small}\}$\\ Let $\mathbf{\Gamma_{large}
   (v)}:=\{\tilde{v}\in V_{large} : (v,\tilde{v})\in E_{large}\}$
 \end{notation}
-Suppose $p=(u,v)$, where $u\in V_{small}$ and $v\in V_{large}$, $s$ is
-a state of the matching procedure, $M(s)$ is consistent mapping by
-$PT$ and $lab(u)=lab(v)$.  $Cons_{PT}(p,M(s))$ checks whether
-including pair $p$ into $M(s)$ leads to a consistent mapping by $PT$.
 
-\subsubsection{Induced subgraph isomorphism}
 $M(s)\cup \{(u,v)\}$ is a consistent mapping by $IND$ $\Leftrightarrow
 (\forall \tilde{u}\in M_{small}: (u,\tilde{u})\in E_{small}
-\Leftrightarrow (v,Pair(M(s),\tilde{u}))\in E_{large})$.\newline The
+\Leftrightarrow (v,Pair(M(s),\tilde{u}))\in E_{large})$. The
 following formulation gives an efficient way of calculating
 $Cons_{IND}$.
 \begin{claim}
@@ -596,74 +595,27 @@
   consistency function in the case of $IND$.
 \end{claim}
 
-\subsubsection{Graph isomorphism}
-$M(s)\cup \{(u,v)\}$ is a consistent mapping by $ISO$
-$\Leftrightarrow$ $M(s)\cup \{(u,v)\}$ is a consistent mapping by
-$IND$.
-\begin{claim}
-$Cons_{ISO}((u,v),M(s))$ is a consistency function by $ISO$ if and
-  only if it is a consistency function by $IND$.
-\end{claim}
-\subsubsection{Subgraph isomorphism}
-$M(s)\cup \{(u,v)\}$ is a consistent mapping by $SUB$ $\Leftrightarrow
-(\forall \tilde{u}\in M_{small}:\\(u,\tilde{u})\in E_{small}
-\Rightarrow (v,Pair(M(s),\tilde{u}))\in E_{large})$.
-\newline
-The following formulation gives an efficient way of calculating
-$Cons_{SUB}$.
-\begin{claim}
-$Cons_{SUB}((u,v),M(s)):= (\forall \tilde{u}\in \Gamma_{small}(u)
-  \ \cap\ M_{small}(s):\\(v,Pair(M(s),\tilde{u}))\in E_{large})$ is a
-  consistency function by $SUB$.
-\end{claim}
-
 \subsection{Cutting rules}
 $Cut_{PT}(p,M(s))$ is defined by a collection of efficiently
 verifiable conditions. The requirement is that $Cut_{PT}(p,M(s))$ can
 be true only if it is impossible to extended $M(s)\cup \{p\}$ to a
 whole mapping.
+
+As an example, the cutting function of induced subgraph isomorphism is presented.
 \begin{notation}
-
 Let $\mathbf{\tilde{T}_{small}}(s):=(V_{small}\backslash
 M_{small}(s))\backslash T_{small}(s)$, and
 \\ $\mathbf{\tilde{T}_{large}}(s):=(V_{large}\backslash
 M_{large}(s))\backslash T_{large}(s)$.
 \end{notation}
-\subsubsection{Induced subgraph isomorphism}
+
 \begin{claim}
 $Cut_{IND}((u,v),M(s)):= |\Gamma_{large} (v)\ \cap\ T_{large}(s)| <
   |\Gamma_{small} (u)\ \cap\ T_{small}(s)| \vee |\Gamma_{large}(v)\cap
   \tilde{T}_{large}(s)| < |\Gamma_{small}(u)\cap
   \tilde{T}_{small}(s)|$ is a cutting function by $IND$.
 \end{claim}
-\subsubsection{Graph isomorphism}
-Note that the cutting function of induced subgraph isomorphism defined
-above is a cutting function by $ISO$, too, however it is less
-efficient than the following while their computational complexity is
-the same.
-\begin{claim}
-$Cut_{ISO}((u,v),M(s)):= |\Gamma_{large} (v)\ \cap\ T_{large}(s)| \neq
-  |\Gamma_{small} (u)\ \cap\ T_{small}(s)| \vee |\Gamma_{large}(v)\cap
-  \tilde{T}_{large}(s)| \neq |\Gamma_{small}(u)\cap
-  \tilde{T}_{small}(s)|$ is a cutting function by $ISO$.
-\end{claim}
 
-\subsubsection{Subgraph isomorphism}
-\begin{claim}
-$Cut_{SUB}((u,v),M(s)):= |\Gamma_{large} (v)\ \cap\ T_{large}(s)| <
-  |\Gamma_{small} (u)\ \cap\ T_{small}(s)|$ is a cutting function by
-  $SUB$.
-\end{claim}
-Note that there is a significant difference between induced and
-non-induced subgraph isomorphism:
-
-\begin{claim}
-\label{claimSUB}
-$Cut_{SUB}'((u,v),M(s)):= |\Gamma_{large} (v)\ \cap\ T_{large}(s)| <
-|\Gamma_{small} (u)\ \cap\ T_{small}(s)| \vee |\Gamma_{large}(v)\cap
-\tilde{T}_{large}(s)| < |\Gamma_{small}(u)\cap \tilde{T}_{small}(s)|$
-is \textbf{not} a cutting function by $SUB$.
-\end{claim}
 
 \section{The VF2++ Algorithm}
 Although any total ordering relation makes the search space of VF2 a