# Arc-Completion of 2-Colored Best Match Graphs to Binary-Explainable Best Match Graphs
## 5 Completion of a 2-BMG to a 2-beBMG
As in Case (i), we have \((x^{\prime},y),(y,x^{\prime})\in E(G)\subseteq E(G^{\prime})\). As \(x\in L(T(u))\setminus S_{u}\), we can conclude that \(v\coloneqq\mathsf{par}_{T}(x)\prec_{T}u\) by the definition of support leaves. Therefore, the inner vertex \(v\) is not the root of \(T\) and we can apply Cor. 1 in [20] to conclude that the subtree \(T(v)\) of the inner vertex \(v\) contains both colors. The latter together with Lemma 10 in [21] implies that there are arcs \((x^{\prime\prime},y^{\prime\prime}),(y^{\prime\prime},x^{\prime\prime})\in E (G)\subseteq E(G^{\prime})\) with \(x^{\prime\prime},y^{\prime\prime}\in L(T(v))\) and \(\sigma(x)=\sigma(x^{\prime\prime})\
eq\sigma(y)=\sigma(y^{\prime\prime})\). Note that \(x=x^{\prime\prime}\) is possible. As \(x,x^{\prime\prime},y^{\prime\prime}\) in \(L(T(v))\subset L(T(u))\), \(x^{\prime},y\in L(T(u))\setminus L(T(v))\) and \(v\prec_{T}u\), we can apply Lemma 1 to conclude that \((x^{\prime},y^{\prime\prime}),(y,x),(y,x^{\prime\prime})\in E(G)\subseteq E(G^ {\prime})\) and \((y^{\prime\prime},x^{\prime}),(x,y),(x^{\prime\prime},y)\
otin E(G)\subseteq E (G^{\prime})\). Together with \((x^{\prime},y),(y,x^{\  
completion of BMGs to beBMGs, resulting in a simple, polynomial-time algorithm for this problem. This result is primarily of theoretical interest. In contrast to the 2-colored case, \(\ell\)-BMG CBEG with a BMG as input and \(\ell\geq 3\) in general does not have a unique optimal solution. In the example in Figure 2, the missing arcs \((a_{2},b_{1})\) and \((b_{2},a_{1})\) in the induced hourglass \([a_{1}b_{1}\succsim_{a}a_{2}b_{2}]\) must be inserted. The resulting digraph is not a BMG. To obtain a beBMG, it suffices to insert in addition either the arc \((c,a_{1})\) or the arc \((c,b_{1})\) (cf. Proposition 3). We suspect, therefore, that \(\ell\)-BMG CBEG does not admit an efficient solution in general. The solutions of 2-BMG CBEG problems for all 2-colored induced subgraphs that are not binary-explainable are nevertheless an appealing starting point for constructing heuristics for \(\ell\)-BMG CBEG. We refer to the work in [17] for a detailed analysis of a class of approximation algorithms for BMG and beBMG modification. The simple solution of 2-BMG CBEG begs the question whether other arc modification problems for beBMGs, in particular the corresponding deletion and editing problems, have a similar structure. This does not seem to be case however. Neither 2-BMG CBEG nor 2-BMG CBEG with a 2-BMG as input has a unique optimal solution. To see this, consider the 2-BMG consisting of the hourglass \([xy\succsim_{x}^{\gamma}x^{\prime}y^{\prime}]\) which is explained by the unique non-binary tree \((x,y,(x^{\prime},y^{\prime}))\) (in Newick format, see also Figure 1A). Deletion of the arcs \((x,y)\) or \((y,x)\) results in a digraph that is explained by the binary trees \((y,(x,(x^{\prime},y^{\prime})))\) or \((x,(y,(x^{\prime},y^{\prime})))\), respectively. We suspect that a BMG as input does not make these problems easier than the general case--the complexity of which remains an open question however. Conceptualization, D.S., M.G., M.H. and P.F.S. ; formal analysis, D.S., M.G., M.H. and P. F.S. ; methodology, D.S., M.G., M.H. and P. F.S. ; writing--original draft, D.S., M.G., M.H. and P.F.S. All authors have read and agreed to the published version of the manuscript. This research was funded in part by the German Research Foundation (DFG), the Austrian Federal Ministries BMK and BMDW and the Province of Upper Austria in the frame of the COMET Programme managed by FFG. We acknowledge support from Leipzig University for Open Access Publishing. Not applicable. The authors declare no conflict of interest. Figure 2: Example for 3-BMG CBEG with the 3-BMG \((G,\sigma)\) (explained by the LRT \((T,\sigma)\)) as input that has no unique optimal solution. Insertion of the missing arcs \((a_{2},b_{1})\) and \((b_{2},a_{1})\) produces a digraph that is not a BMG.