Steiner Tree Problem in Phylogeny with Given Topology

• INSTANCE: Set of characters $C = {1, \cdots m}$ , for each $i\in C$ a set $A_i$ of states of character $i$ , $\lambda\colon S\to L(T)$ between $S$ and the set $L(T)$ of leaves of $T$

• SOLUTION: An assignment $a\colon V(T)\setminus L(T)\to A_1\times \cdots \times A_m$ .

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

• OBJECTIVE: Minimize.

• Approx.: Admits a PTAS [104].

• Comment: This is a special case of the Tree Alignment with a Given Phylogeny.