# Arc-Completion of 2-Colored Best Match Graphs to Binary-Explainable Best Match Graphs
## 1 Introduction  
Best match graphs (BMGs) are vertex-colored digraphs that appear in mathematical phylogenetics as a representation of a gene's evolutionary closest relatives in another species [1, 2]. That is, given a rooted tree \(T\), a vertex (gene) \(x\) in the BMG \(G(T,\sigma)\) is colored by the species \(\sigma(x)\) in which it resides, and there is an arc \((x,y)\) if there is no other gene \(y^{\prime}\) in species \(\sigma(y^{\prime})=\sigma(y)\
eq\sigma(x)\) with a later last common ancestor than the last common ancestor \(\operatorname{lca}_{T}(x,y)\) of \(x\) and \(y\) in \(T\). Although rooted trees are crucial for the definition of BMGs, they are, however, unknown in practice, and we are often only left with estimates of their BMGs. In general, there are multiple trees that \"explain\" the same BMG. There is, however, a unique least resolved tree (LRT) for each BMG, which can be obtained from \(T\) by contracting certain edges [1]. The LRTs will play a central role in this contribution. The subgraph of a BMG induced by the vertices of some subset of colors is again a BMG. Every BMG therefore can be viewed as the disjoint union of (the arc sets of) 2-colored BMGs (2-BMGs). These 2-BMGs [1, 3, 4] are bipartite and form a common subclass of the _sink-free_ digraphs [5, 6] and the _bi-transitive_ digraphs [7].  
Estimates of graphs from real-life data tend to be affected by noise and thus typically will violate the defining properties of the desired graph class. The solution of a corresponding graph modification problem [8] therefore can by employed as a means of noise reduction, see, e.g., in [9]. The arc modification problems (deletion, completion, and editing) for BMGs are NP-complete, in general [10], and remain hard even for the special case of 2 colors.  
Phylogenetic trees are often considered to be binary in theory. Most polytomies are therefore considered a limitation of the available data or method of tree reconstruction [11; 12] rather than a biological reality [13; 14]. In the setting of BMGs, this distinction is important because not all BMGs can be derived from binary gene trees. Instead, _binary-explainable_ BMGs (beBMGs) form a proper subclass [15] that is distinguished by a single forbidden induced subgraph, the _hourglass_, from other BMGs [16]. As \"true phylogenies\" are often assumed to be binary, BMGs that are not binary-explainable will be considered as a poor model. It is of interest, therefore, to consider the problem of modifying a BMG to a beBMG. Conceptually, this is similar to fully resolving phylogenetic trees starting from a tree with multifuractions. The arc modification problems for beBMGs are, as the more general case, NP-complete [10; 15]. Thus, heuristic algorithms must be employed in practice [17]. It is useful to know, therefore, whether an approximation of a graph by a BMG that is not binary-explainable may be helpful towards finding a beBMG. That is, whether a solution to the more general problem makes is easier to find a solution of the constrained problem. To this end, we naturally ask whether the problem of modifying a BMG to a beBMG is as difficult as the general case. It is, in fact, not unusual that graph modification problems that are hard in general become easy when the input is confined to a--usually restrictive--class of graphs, see, e.g., in [18; 19]. Here, we show that the problem of completing a 2-colored BMG to a beBMG can indeed be solved in polynomial time.  
To prove this result, we make use of the fact that every BMG is associated with a unique _least resolved tree_ (LRT). Theorem 1 shows that the property of being the LRT for some BMG is preserved under contraction of inner edges. This observation leads to the explicit construction of a \"collapsed tree\" from the LRT of the input BMG \((G,\sigma)\), which not only is the LRT of a 2-colored beBMG, but also minimizes the number of arcs that need to be inserted to obtain a beBMG from \((G,\sigma)\). The construction does not generalize to more than 2 colors.