Fig. 3

Extraneous clades and R-RF(+) and EF-R-RF(+) completions. This figure shows two trees S and T with partial leaf set overlap whose optimal completions under the R-RF(+) problem result in extraneous clades. The tree S contains two leaves c and d that are absent from T, and the tree T contains two leaves i and j absent from S. The lower-right part of the figure shows optimal completions of S and T, labeled \(S''\) and \(T''\), respectively, that minimize the RF distance over all possible completions. The nodes marked in red denote (non-leaf) clades common to both \(S''\) and \(T''\). Observe that of the three nodes that \(S''\) and \(T''\) have in common, the lower two, i.e., \(\{c, i\}\) and \(\{d, j\}\), are extraneous clades that have no support in either S or T and do not contain any of the leaves shared by both S and T. Optimal completions under EF-R-RF(+) disallow such extraneous clades. The upper-right part of the figure shows optimal completions of S and T that minimize the RF distance over all completions without any extraneous clades. The completions \(S'\) and \(T'\) only contain clades that have at least one leaf shared by both trees