# Arc-Completion of 2-Colored Best Match Graphs to Binary-Explainable Best Match Graphs
## 5 Completion of a 2-BMG to a 2-beBMG  
Writing \(G+F\coloneqq(G,E\cup F)\) for a digraph \(G=(V,E)\) and arc set \(F\subseteq V\times V\setminus\{(v,v)\mid v\in V\}\), consider the following graph completion problem:  
**Problem 1** (2-BMG Completion restricted to Binary-Explainable Graphs (2-BMG CBEG)). : \begin{tabular}{l l} Input: & _A properly 2-colored digraph \((G=(V,E),\sigma)\) and an integer \(k\)._ \\ Question: & _Is there a subset \(F\subseteq V\times V\setminus(\{(v,v)\mid v\in V\}\cup E)\) such that_ \\  & \(|F|\leq k\) _and_ \((G+F,\sigma)\) _is a binary-explainable 2-BMG?_ \\ \end{tabular}   
In the general case, 2-BMG CBEG is NP-complete ([10], Cor. 5.11). Here, we are interested in the restriction of the 2-BMG CBEG problem with BMGs as input. The following result holds for BMGs and their completions to beBMGs with an arbitrary number of colors. Lemma 2: _Let \((G^{\prime},\sigma)\) be a completion of a BMG \((G,\sigma)\) to a beBMG, and let \(\{xy\succsim_{x}^{x}x^{\prime}y^{\prime}\}\) be an induced hourglass in \((G,\sigma)\). Then, \((G^{\prime},\sigma)\) contains both arcs \((x^{\prime},y)\) and \((y^{\prime},x)\)._  
Proof. : It is shown in ([1], Obs. 1) that the subgraphs of a BMG induced by all vertices with any two given colors is a 2-BMG. As \((G^{\prime},\sigma)\) is a (binary-explainable) BMG, all of its 2-colored induced subgraphs are therefore 2-BMGs. By assumption, \((G,\sigma)\) is not binary-explainable as it contains the hourglass \([xy\succsim_{x}^{x}x^{\prime}y^{\prime}]\) as an induced subgraph (cf. Proposition 3). The hourglass contains all possible arcs between vertices of different colors except \((x^{\prime},y)\) and \((y^{\prime},x)\). As \((G^{\prime},\sigma)\) contains no hourglass and \(G^{\prime}\) is a completion of \(G\), i.e., \(E(G)\subseteq E(G^{\prime})\), we conclude that \((G^{\prime},\sigma^{\prime})\) contains at least one of the arcs \((x^{\prime},y)\) and \((y^{\prime},x)\). Assume for contradiction that, w.l.o.g., \((G^{\prime},\sigma^{\prime})\) only contains \((x^{\prime},y)\). We have \((y^{\prime},x^{\prime})\), \((y,x)\in E(G^{\prime})\) and \(\sigma(y^{\prime})=\sigma(y)\
eq\sigma(x^{\prime})=\sigma(x)\) by the definition of hourglasses, and by assumption \((x^{\prime},y)\in E(G^{\prime})\) and \((y^{\prime},x)\
otin E(G^{\prime})\). Therefore, the four vertices \(x,x^{\prime},y,y^{\prime}\) induce an F2-graph in \((G^{\prime},\sigma)\). By Proposition 4, the 2-colored subgraph of \((G^{\prime},\sigma)\) induced by the two colors \(\sigma(x)\) and \(\sigma(y)\) is not a BMG. Consequently, \((G^{\prime},\sigma^{\prime})\) is not a BMG either, it is a contradiction. Therefore, \((G^{\prime},\sigma)\) contains both arcs \((x^{\prime},y)\) and \((y^{\prime},x)\). Definition 8: _Let \((T,\sigma)\) be a tree with a 2-colored leaf set, i.e., \(|\sigma(L(T))|=2\). Denote by \((T^{*},\sigma)\) the collapsed tree obtained from \((T,\sigma)\) by contraction of all inner edges in \(T(u)\) for all \(u\in V^{0}(T)\) that have support leaves of both colors._  
In other words, \((T^{*},\sigma)\) is obtained from \((T,\sigma)\) by collapsing every subtree \(T(u)\) to a star if \(u\) has support leaves of both colors. Lemma 3: _The collapsed tree \((T^{*},\sigma)\) of \((T,\sigma)\) is uniquely defined and can be computed from \((T,\sigma)\) in \(O(|V(T)|)\)-time._Proof. : The collapsed tree \((T^{*},\sigma)\) is well defined because whenever \(v\prec_{T}u\), collapsing the subtree \(T(v)\) to a star does not change the set of support leaves \(S_{u}\). Similarly, collapsing \(T(v)\) if \(v\) is not \(\prec_{T}\)-comparable with \(u\) does not change \(S_{u}\). Thus, \((T^{*},\sigma)\) is uniquely defined. To see that \((T^{*},\sigma)\) can be computed in \(O(|V(T)|)\) operations, we observe that it suffices to collapse all subtrees \(T(u)\) such that \(u\in V^{0}(T)\) has support leaves of both colors and there is no \(u^{\prime}\prec_{T}u\) with this property, i.e., \(u\) is \(\preceq_{T}\)-maximal in that sense.