# Progressive Multiple Alignment of Graphs
## 3 Algorithmic Considerations
### Computing Optimal Common Induced Subgraphs
```
Data: Graphs \(G_{1}\) and \(G_{2}\) with \(|V(G_{1})|\geq|V(G_{2})|\), anchor matching \(M^{*}\) Result: Set \(\mathcal{M}\) of maximal common induced subgraphs \(\mathcal{M}\leftarrow\emptyset\); \(R\leftarrow\) vertices of \(G_{2}\) not part of \(M^{*}\); for all subsets \(S\) of \(R\) in order of increasing cardinality do // the iteration over \(S\) can be restricted, see text \(G^{\prime}\gets G_{2}[V(G_{2})\setminus S]\); \(\mathcal{M}\leftarrow\mathcal{M}\cup\text{VF2\_sgi}(G_{1},G^{\prime},M)\); // VF2_sgi\((G_{1},G^{\prime},M^{*})\) returns all embeddings \(M\) of \(G^{\prime}\) in \(G\) with \(M^{*}\subseteq M\), if any end return\(\mathcal{M}\)
```  
**Algorithm 1**Iterative_Trimming\((G_{1},G_{2},M^{*})\)  
The basic step of the VF2-like approach is formalized in Algorithm 2. To compute the MCIS of \(G_{1}\) and \(G_{2}\) with a possibly empty set \(M^{*}\) of anchor matches, one calls \(\texttt{VF2\_step}(G_{1},G_{2},M^{*})\). The end result is the set \(\mathcal{M}\) of all maximal matchings containing \(M^{*}\) that correspond to a maximal common induced subgraph. During the recursive traversal of the search tree, a set of extension candidates \(P\) is computed for a the current matching \(M\). If \(M\) cannot be extended, i.e., if there is no compatible match \((x,y)\in P\) for \(M\), then \(M\) forms a leaf in the search tree and is added to result set \(\mathcal{M}\). Assuming a strictly monotone scoring function, the set of matches of a score-maximal pairwise alignment is necessarily maximal w.r.t. cardinality [30; 45]. It therefore suffices to evaluate the scores of the matchings \(M\) at the leaves of the search tree constructed by \(\texttt{VF2\_step}()\). The computation of the candidate matches, Algorithm 3, depends on a fixed total order of the vertices of the smaller graph \(G_{2}\). In order to avoid the duplication of branches in the search tree, only matches of vertices in \(G_{2}\) following all vertices in matches of \(M\), except those of a possible anchor, are considered. It is convenient to choose the order such that the vertices in \(G_{2}\) that are part of the anchor are numbered \(1,2,\ldots,|M^{*}|\). The routine \(\texttt{VF2\_sgi}()\) in Iterative_Trimming\(()\) is similar to \(\texttt{VF2\_step}()\), except for further heuristic optimizations to speed up the decision of whether \(G_{2}\) is isomorphic to a subgraph of \(G_{1}\) or not. The implementation of both routines is adapted to handle ambiguous edges and comparing vertex and edge labels when requested by the user, and can be set to optimize a monotone scoring function instead of the number of vertices in the MCIS as well. ```
Data: Graphs \(G_{1}\) and \(G_{2}\), with total order \(\leq\) over \(V(G_{2})\), a matching \(M\in V(G_{1})\times V(G_{2})\) Result: Set \(\mathcal{M}\) of all matchings between \(G_{1}\) and \(G_{2}\). \(M\)leaf\(\leftarrow\) true; \(P\leftarrow\)candidate_matches\((G_{1},G_{2},M)\); for\((x,y)\in P\)do if\(\textit{compatible}(M,(x,y))\)then \(M\gets M\cup\{(x,y)\}\) ;  Mleaf\(\leftarrow\)false ;  VF2_step\((G_{1},G_{2},M)\) ;  end if ifMleafthen \(\mathcal{M}\leftarrow\mathcal{M}\cup\{M\}\)  end if
```  
**Algorithm 2**VF2_step\((G_{1},G_{2},M)\)  
```
Data: Graphs \(G_{1},G_{2}\) and a matching \(M\subset V(G_{1})\times V(G_{2})\) Result: Set \(P\) of match candidates for extending \(M\)\(N_{1}\leftarrow\) set of unmatched vertices in \(V(G_{1})\); \(N_{2}\leftarrow\) set of unmatched vertices in \(V(G_{2})\); // the anchor \(M^{*}\) is contained in \(M\) and would be excluded from the candidates \(n_{2}\leftarrow\max(0,\max\{y|(x,y)\in M\})\); \(P\leftarrow\{(x,y)|x\in N_{1},\,y\in N_{2},\,y>n_{2},\,\}\); return\(P\)
```  
**Algorithm 3**candidate_matches\((G_{1},G_{2},M)\)  
The original formulation of the VF2 algorithm differs from our adaptation VF2_step\(()\) for MCIS-search by using a different algorithm candidate_matches\(()\) for proposing candidates for matches that extend \(M\).