Steiner Tree Problem in Phylogeny

• INSTANCE: $C = {1, \cdots m}$ set of Characters, for each $i\in C$ , set of states $A_i$ of character $i$ , $S \subseteq A_1\times \cdots \times A_m$ set of species.

• SOLUTION: A tree $T = (V_T, E_T)$ with $S \subseteq V_T \subseteq A_1\times \cdots \times A_m$

• COST FUNCTION: ${\displaystyle\sum_{e = {u,v} \in E_T}} d_H(u,v)$ , where $d_H$ denotes the Hamming distance [48].

• OBJECTIVE: Minimize.

• Approx.: Approximable within approximation ratio $\ln (4)+\epsilon$ for every $\epsilon >0$ [4],[65].

• Hardness: NP-hard [48].

• Comment: A phylogeny for a set of n distinct species $S$ is a tree whose leaves are all elements of S and where $S \subseteq V(T) \subseteq A_1\times \cdots \times A_m$ .