# Similar Supergraph Search Based on Graph Edit Distance
## 7 Customization of Solutions  
In the previous section, we proposed a method for searching for the set of graphs \(S\) defined by Equation (3). The number of graphs reachable by editing graph \(q^{\prime}\)\(\theta\) times in Equation (3) increases exponentially as \(\theta\) is increased. Therefore, for a large \(\theta\), the computation time required to search for the graphs in \(S\) becomes excessively long. However, some real applications need to obtain the following sets of constrained graphs rather than obtaining all the graphs in \(S\). 1. Editing graphs is constrained: for example, the relabeling of vertices or edges is admissible in \(ed(q^{\prime},g_{i})\) of Equation (3), whereas insertions and deletions are not admissible. That is, when converting a labeled graph \(g\) to an unlabeled graph \(un(g)\) by removing label information from vertices and edges in \(g\), \(un(g_{i})\) and \(un(q^{\prime})\) in Equation (3) are isomorphic. 2. Editing graphs is constrained: for example, editing some specific vertices and edges in a query graph \(q\) is admissible, whereas editing other vertices and edges is not admissible. For example, in the substructure drawn with blue lines and labels in Figure 1, editing its ring structure is admissible, whereas editing the remainder of the blue substructure is not admissible. The problem for the above constraint \(\langle 1\rangle\) is formalized as follows. \[\{g_{i}\in G\mid\exists q^{\prime}\subseteq q\,s.t.\,ed(g_{i},q^{\prime}) \leq\theta\wedge un(g_{i})=un(q^{\prime})\}. \tag{16}\]  
In order to solve this problem, Equation (15) is rewritten as follows. \[ed(s,s^{\prime}) \tag{17}\] \[= \begin{cases}\delta^{\prime}(\ell(v_{i}),\ell(v^{\prime}_{i}))+ \sum_{\begin{subarray}{c}1\leq j<i\\ \wedge x_{ij}\
eq 0\\ \wedge x^{\prime}_{ij}\
eq 0\end{subarray}}\delta^{\prime}(x_{ij},x^{\prime}_{ j,i})+\sum_{\begin{subarray}{c}1\leq j<i\\ \wedge(x_{ij}=0\\ \vee x^{\prime}_{ij}=0)\end{subarray}}\infty&(s\
eq null\wedge s^{\prime} \
eq null)\\ \infty&(\textit{otherwise}).\end{cases} \]  
For the case of \(s\
eq null\wedge s^{\prime}\
eq null\), the first and second terms in Equation (17) are the numbers of edits that occur by relabeling the \(i\)-th vertices and edges \((i,j)\)\((1\leq j<i)\)respectively, in \(g\in G\) and \(q^{\prime}\). The third term of Equation (17) is the sum of the numbers of edits that occur by inserting or deleting edges. For this case, in containing such insertion or deletion operations, the \(ed(s,s^{\prime})\) function returns values larger than \(\theta\) and Algorithm 4 (in Line 7) backtracks the code tree. For the case of the above constraint \(\langle 2\rangle\), let some specific vertices in query graph \(q\) be \(V_{q}\subseteq V(q)\). When Algorithm 4 visits node \(n\) in the code tree, it generates various codes by \(\langle w_{1},w_{2},\ldots,w_{h},w\rangle\), in Line 4. Some vertices in \(\langle w_{1},w_{2},\ldots,w_{h},w\rangle\) are included in \(V_{q}\), but others are not. In this case, Equation (15) is rewritten as follows. \[ed(s,s^{\prime}) \tag{18}\] \[= \begin{cases}\delta^{\prime}(\ell(v_{i}),\ell(v_{i}^{\prime}))+ \sum_{\begin{subarray}{c}w_{j}\in V_{q}\\ \wedge 1\leq j<i\\ \wedge x_{ij}\
eq 0\end{subarray}}\delta^{\prime}(x_{j,i},x_{j,i}^{\prime})+ \sum_{\begin{subarray}{c}w_{j}\in V_{q}\\ \wedge 1\leq j<i\\ \wedge x_{ij}\
eq 0\end{subarray}}\infty&(s,s^{\prime}\
eq null\wedge w_{i}\in V _{q})\\ \infty&(otherwise).\end{cases} \]  
Thus, for the case of \(s\
eq null\wedge s^{\prime}\
eq null\wedge w_{i}\in V_{q}\), the first and second terms of Equation (18) are the numbers of edits that occur by relabeling the \(i\)-th vertices and edges \((i,j)\)\((1\leq j<i)\), respectively, in \(g\in G\) and \(q^{\prime}\), where \(w_{i}\) and \(w_{j}\) are elements in \(V_{q}\). The third term of Equation (18) is the sum of the numbers of edits that occur by editing the other vertices and edges.