# Progressive Multiple Alignment of Graphs
## 3 Algorithmic Considerations
### Computing Optimal Common Induced Subgraphs  
As discussed in Section 2.6, optimal pairwise alignments are based on score-optimal common induced subgraphs, which in turn are maximal common induced subgraphs. Computing MCIS is known to be computationally hard. The corresponding decision problem is NP-complete [37] and hard to approximate [38]. For small graphs with limited degree and non-trivial labels, such as in particular molecule graphs, it is nevertheless feasible to solve MCIS exactly. Probably the best known algorithmic approach is to compute the modular product of \(G\oplus H\) using the fact that an MCIS of \(G\) and \(H\) corresponds to a maximum clique in \(G\oplus H\)[39]. It is not obvious, however, how ambiguous edges can be handled efficiently in this setting. The main alternative is a class of search procedures based on the step-wise extension of a matching \(M\subseteq V(G)\times V(H)\) by candidate matches \(xy\) with \(x\in V(G)\) and \(y\in V(H)\). These algorithms are designed for the subgraph isomorphism problem, i.e., to recognize whether the smaller of the two input graphs, \(G_{2}\), is isomorphic to an induced subgraph of the larger one, \(G_{1}\), [23; 24]. Starting from the empty set of matches, this yields a search tree whose leaves are the maximal induced common subgraphs. A positive answer to the subgraph isomorphism problem corresponds to a leaf in which \(V(G_{2})\) is matched in its entirety. [PERSON] and similar algorithms combine the extension of \(M\) with bounds on the number of possible extending matches in order to obtain a full-fledged branch-and-bound approache [40; 41; 42]. It is not clear, however, how good bounds can be obtained in the presence of ambiguous edges and arbitrary compatibility rules for the labels of vertices and edges. Our implementations thus focus on the enumeration of maximal common induced subgraphs. In order to accommodate prior knowledge, it is sometimes of interest to compute alignments that incorporate an _anchor_, i.e., set of matches \(M^{*}\) that are given as part of the input. For sequence alignments, this idea has been explored, e.g., in CONREAL[43] and an anchored version of dialign, both with applications of phylogenetic footprinting [44]. The idea of anchors generalizes to graph alignments in a straightforward manner. Instead of starting from an empty set of matches \(M=\varnothing\), we can insist that any valid set of matches \(M\) contains the anchor matches, \(M^{*}\subseteq M\). This is trivially enforced in VF2-like approaches,where anchors lead to a drastic reduction in the search space since only the subtree rooted at the anchor matches \(M^{*}\) needs to be processed. If the MCIS is expected to be small compared to both \(G_{1}\) and \(G_{2}\), then a direct, VF2-like expansion of the matches set \(M\) appears to be the most promising strategy. If the solution is expected to cover most of \(G_{2}\), a viable alternative is to \"trim\" \(G_{2}\) by removing some of its vertices; see Algorithm 1. An optimized subgraph isomorphism test, denoted by \(\texttt{VF2\_sgi}()\) in Algorithm 1, can then be used to decide whether the trimmed induced subgraph \(G_{2}^{\prime}\) of \(G_{2}\) appears as a subgraph in \(G_{1}\). This allows us to use many of the optimizations in VF2 that are not applicable if all maximal common subgraphs need to be enumerated. The iteration over the sets \(S\) of removed vertices can be restricted to terminate at the cardinality \(|S|\) at which the first match \(M\) is encountered as in our current implementation. While a recursive version of such a trimming algorithm could also be implemented, it seems difficult to make use of latter bound in such a setting. Alternatively, it may exclude \(S\) if a non-empty set of matches was returned already for one of its subsets. We note that for arbitrary monotone scores, the latter strategy must be employed since there is no guarantee that the MCIS with the maximum score is also _maximum_ in cardinality.