## 2 Preliminaries  
An _evolutionary tree (phylogenetic tree)_ on a set, \(S\), of \(n\) species, \(|S|=n\), is a rooted binary (More precisely, an evolutionary tree can also be unrooted; however, triplet-based methods output rooted phylogenies)unordered tree in which leaves are distinctly labeled by members of \(S\) (see Figure 1(a)). A _rooted triplet_ is a phylogenetic tree with three leaves. The unique triplet of leaves, \(x\), \(y\), \(z\), is denoted by ((_x_, _y_), _z_) or _xy_\(|\)_z_, if the lowest common ancestor of \(x\) and \(y\) is a proper descendant of the lowest common ancestor of \(x\) and \(z\) or, equivalently, if the lowest common ancestor of \(x\) and \(y\) is a proper descendant of the lowest common ancestor of \(y\) and \(z\) (see Figure 1(b)). A triplet, \(t\) (e.g., _xy_\(|\)_z_) is _consistent_ with a tree, \(T\), or, equivalently, \(T\) is consistent with _t_) if \(t\) is an embedded subtree of \(T\). This means that \(t\) can be obtained from \(T\) by a series of edge contractions (_i.e._, if in \(T\), the lowest common ancestor of \(x\) and \(y\) is a proper descendant of the lowest common ancestor of \(x\) and _z_). We also say _T satisfies t_, if \(T\) is consistent with \(t\). The tree in Figure 1(a) is consistent with the triplet in Figure 1(b). A phylogenetic tree, \(T\), is consistent with a set of rooted triplets if it is consistent with every triplet in the set. We call two leaves _siblings_ or a _cherry_ if they share the same parent. For example, \(\{x,y\}\) in Figure 1(a) form a cherry.  
A set of triplets, \(R\), is called _dense_ if for each set of three species, \(\{x\), \(y\), \(z\}\), \(R\), contains at least one of three possible triplets, \(xy|z\), \(xz|y\) or \(yz|x\). If \(R\) contains exactly one triplet for each set of three species, it is called _minimally dense_, and if it contains every possible triplet, it is called _maximally dense_. Now, we can define the problem of reconstructing an evolutionary tree from a set of rooted triplets. Suppose \(S\) is a finite set of species of cardinality, \(n\), and \(R\) is a finite set of rooted triplets of cardinality, \(m\), on \(S\). The problem is to find an evolutionary tree leaf-labeled by members of \(S\), which is consistent with the maximum number of rooted triplets in \(R\). This problem is called the _Maximum Rooted Triplets Consistency (MaxRTC)_ problem [5] or the _Maximum Inferred Local Consensus Tree (MILCT)_ problem [6]. This problem is NP-hard (see Section 3), which means no polynomial-time algorithm can be found to solve the problem optimally unless P= NP. For this and similar problems, one might search for polynomial-time algorithms that produce approximate solutions. We call an algorithm an _approximation algorithm_ if its solution is guaranteed to be within some factor of optimum solution. In contrast, _heuristics_ may produce good solutions, but do not come with a guarantee on their quality of solution. An algorithm for a maximization problem is called an \(\alpha-approximation\) algorithm, for some \(\alpha>1\), if for any input, the output of the algorithm is at most \(\alpha\)-times worse than the optimum solution. The factor, \(\alpha\), is called the _approximation factor_ or _approximation ratio_.