## 3 Algorithm for a Restricted Case
For another example, the score is \(-\infty\) for each of alignments, \(((u_{1},u_{3}),(v_{4},v_{5}))\), \(((u_{1},u_{2}),(v_{1},v_{2}))\) and \(((u_{3}),(v_{3}))\), whereas the score of \(((u_{2}),(v_{3}))\) is 2, since \(\{u,u^{\prime}\}\
otin E\), \(\{v,v^{\prime}\}\
otin E\), \(l(u_{2},v_{3})=1\), \(r(u_{2},v_{3})=1\) and \(MCS_{c}(G_{1}(u_{2}),G_{2}(v_{3}))=0\). It is to be noted that vertices not appearing in an alignment can match in a later dynamic programming process; for example, \(u_{2}\) can match with \(v_{2}\) under an alignment of \(((u_{1},u_{3}),(v_{1},v_{4}))\), although edges \(\{u,u_{2}\}\) and \(\{v,v_{2}\}\) are ignored. As in the case of \(SimpleOuterMCS_{b}(G_{1}(u,C),G_{2}(v,D))\), \(SimpleOuterMCS_{p}\)\((G_{1}(u,u^{\prime}),G_{2}(v,v^{\prime}))\) can be modified into a dynamic programming version. Then, we have the following theorem:  
**Theorem 1**: _SIMPLE-OUTER-MCS can be solved in polynomial time._  
Proof. First we consider the correctness of the algorithm \(SimpleOuterMCS(G_{1},G_{2})\). The crucial points of the algorithm are that it examines all possible combinations of the neighbors via alignments examined in \(SimpleOuterMCS_{b}(G_{1}(u,C),G_{2}(v,D))\) for each pair of cut vertices \((u,v)\) and via alignments examined in \(SimpleOuterMCS_{p}(G_{1}(u,u^{\prime}),G_{2}(v,v^{\prime}))\) for each pair of cut pairs \(((u,u^{\prime}),(v,v^{\prime}))\), where the connectedness in the latter case is taken care of by the use of \(l(u_{i},v_{j})\) and \(r(u_{i},v_{j})\). It should be noted that non-neighbors of \(u\) cannot be neighbors of a node corresponding to \(u\) in MCS, and the ordering of neighbors must be preserved by Fact 1. Therefore, examination of all alignments covers all valid combinations of neighbors. Based on these facts, it is straightforward to see that \(SimpleOuterMCS(G_{1},G_{2})\) correctly computes the size of MCS. Next, we consider the time complexity. Since we examine \(O(n^{2})\) possible root pairs, we focus on the case where the roots are fixed, where \(n\) is the maximum number of vertices in \(G_{1}\) and \(G_{2}\). Although \(SimpleOuterMCS(G_{1},G_{2})\) is described as a recursive algorithm, the numbers of required scores of \(MCS(G_{1}(u),G_{2}(v))\), \(MCS(G_{1}(u,C),G_{2}(v,D))\) and \(MCS(G_{1}(u,u^{\prime}),G_{2}(v,v^{\prime}))\) are \(O(n^{2})\), \(O(n^{2})\) and \(O(n^{4})\), respectively. Therefore, by storing these values in some tables, we can transform \(SimpleOuterMCS\)\((G_{1},G_{2})\) into a dynamic programming algorithm. Computation of \(MCS(G_{1}(u),G_{2}(v))\) can be done in \(O(n^{3})\) time per call, because a maximum weight bipartite matching can be computed in \(O(n^{3})\) time [22]. Using the dynamic programming version, the computation of each of \(MCS(G_{1}(u,C),\,G_{2}(v,D))\) and \(MCS(G_{1}(u,u^{\prime}),G_{2}(v,v^{\prime}))\) can be done in \(O(h^{2}k^{2})\leq O(n^{4})\) time per call. Therefore, the total time complexity is \(O(n^{2})\times(O(n^{2})\times O(n^{3})+O(n^{2})\times O(n^{4})+O(n^{4})\times O (n^{4}))=O(n^{10})\). \(\Box\)  
Though it might be possible to substantially reduce the degree of polynomial by some simplification, as done in [11], we do not go further, because our main purpose is to present a polynomial-time algorithm for the non-restricted (but bounded degree) case.