# Similar Supergraph Search Based on Graph Edit Distance
## 4 Straightforward Method for Constrained Problem
Lemma 4: _Given the two AcGM codes \(c\) and \(c^{\prime}\) defined in Equations (6) and (7), we have the following._  
\[ed(g(c),g(c^{\prime}))\leq ed(c,c^{\prime}). \tag{9}\]  
Proof: According to Equation (2), \(ed(g(c),g(c^{\prime}))\leq ed(c,c^{\prime})\) is obvious. Lemma 5: _Given an arbitrary AcGM code \(c^{\prime}\) of a graph \(g^{\prime}\), the graph edit distance between \(g\) and \(g^{\prime}\) is the following._  
\[ed(g,g^{\prime})\leq\min_{c\in\Omega(g)}ed(c,c^{\prime}). \tag{10}\]  
Proof: Let \(\Omega^{+}(g)\) be codes generated from all possible permutations of vertices in \(g\). So \(\Omega^{+}(g)=\{code(g,\langle u_{1},u_{2},\ldots,u_{|V(g)|}\rangle)\mid\langle u _{1},u_{2},\ldots,u_{|V(g)|}\rangle\in\Phi(|V(g)|,\langle|V(g)|)\supseteq \Omega(g)\). Some codes \(c^{+}\) in \(\Omega^{+}(g)\) are not AcGM codes because a prefix of the permutation from which \(c^{+}\) is generated may not induce a connected subgraph of \(g\). Since \(\Omega^{+}(g)\) are codes generated from all possible permutations of vertices in \(g\), we have \(ed(g,g^{\prime})=\min_{c\in\Omega^{+}(g)}ed(c,c^{\prime})\). In addition, because \(\Omega(g)\subseteq\Omega^{+}(g)\), we have \(\min_{c\in\Omega^{+}(g)}ed(c,c^{\prime})\leq\min_{c\in\Omega(g)}ed(c,c^{ \prime})\). Therefore,  
\[ed(g,g^{\prime})=\min_{c\in\Omega^{+}(g)}ed(c,c^{\prime})\leq\min_{c\in\Omega( g)}ed(c,c^{\prime})\]  
is satisfied. Example 2: _As shown in Figure 4, given two graphs \(g\) and \(q\) for which the edit distance is 3, let an arbitrary AcGM code of \(g\) be \(AAb\). \(\Omega(q)\) is \(\{AAaB0a,AAaB0,ABaA0,BAaA0\}\). When the code AAb is compared with \(AAaB0a\in\Omega(q)\), we need three edits which are indicated as \(\times\) in Figure 4. By comparing \(AAb\) and all elements in \(\Omega(q)\), we obtain the graph edit distance between \(q\) and \(g\) according to Lemma 10._  
From Lemma 5, we have the following corollary. **Colloratory 1**. : _If \(ed(c,c^{\prime})\leq\theta\) for two AcGM codes \(c\) and \(c^{\prime}\), then \(ed(g(c),g(c^{\prime}))\leq\theta\)._  
Algorithm 1 shows the pseudocode for solving the problem defined by Equation (4). In Line 3, an arbitrary AcGM code from \(\Omega(g_{i})\) is generated for graph \(g_{i}\) in database \(G\). After one of all possible AcGM codes for \(q\) is obtained in Line 4, a prefix \(c^{\prime}\), which consists of \(j\) fragments \(c_{i}\), is generated in Line 6. Since \(c^{\prime}\) is a prefix of \(c\), \(g(c^{\prime})\) must be a connected and is an induced subgraph of \(q\). Subsequently, \(g_{i}\) is added to the set of output graphs \(S\) if \(ed(c_{i},c^{\prime})\leq\theta\), which indicates that \(g_{i}\) is a solution in the set defined by Equation (4)  
Figure 4: Computation of Graph Edit Distance using AcGM codes. according to Corollary 1. Once \(g_{i}\) is added to \(S\), any procedures for \(g_{i}\) are stopped and procedures for the next graph \(g_{i+1}\) are started. These steps are repeated for all of the graphs in \(G\). The time complexity of Algorithm 1 is \(O(|\Omega(q)|\sum_{i=1}^{|G|}|V(g_{i})|^{3})\) and the algorithm has some drawbacks, as follows. 1. Although the algorithm produces \(|V(g_{i})|\) prefixes in Line 6 for each AcGM code \(c\) in \(\Omega(q)\) and computes Equation (8) \(|V(g_{i})|\) times in Line 7 for the prefixes, some of the repeated calculations of Equation (8) are redundant because two prefixes \(c^{\prime}\) and \(c^{\prime\prime}\) produced from \(c\) satisfy \(c^{\prime}\subset c^{\prime\prime}\). Using the result of computing \(ed(c_{i},c^{\prime})\) to compute \(ed(c_{i},c^{\prime\prime})\) would render Algorithm 1 efficient. 2. Let \(G_{c}=\{code(g_{i})\mid g_{i}\in G\}\) be the set of codes produced in Line 3. AcGM codes \(code(g_{i})\) and \(code(g_{j})\), for which their prefixes are the same, are included in \(G_{c}\). The repeated calculations of Equation (8) between these AcGM codes and \(c^{\prime}\) are redundant.