How to label a tree with minimum cost? Let $T = (V, E)$ be a tree. Let $\Sigma$ be a finite set of labels. Given a label function $\ell : V \to \Sigma$, the cost of $\ell$ is given by
$$\mu(\ell) = \left| \{(u,v) \in E \mid \ell(u) \neq \ell(v) \} \right|$$
i.e., $\mu(\ell)$ is the number of edges whose vertices have different labels. Given the labels of all leaves of $T$, I would like to find a labeling for internal vertices with the minimum cost $\mu(\ell)$.
I have no idea to solve it. Does anyone have any idea? Thank you in advance! 
 A: Notation Given a tree $T$, let $V(T)$ be the set of its vertices, let $L(T)\subseteq V(T)$ be the set of its leaves. Denote by $T'=T\setminus L(T)$, i.e. let it be the subtree obtained from $T$ removing its leaves. For every $v\in T'$ let $L_v(T)\subseteq L(T)$ be the set of leaves (of $T$) adjacent to $v$.
The idea is the following: let $T$ be a tree with a partial labelling $\ell: L(T)\to\Sigma$ and let $v\in L(T')$. Now, consider the restriction of $\ell$ to $L_v(T)$ and suppose that there is a color $\sigma\in\Sigma$ that appears strictly more often than the others as a value of $\ell|_{L_v(T)}$. Then, a right thing to do (to minimize the cost of a final coloring) is to set the color of $v$ to $\sigma$. 
Indeed, if you consider any coloring $\ell_1:V(T)\to\Sigma$ that extends $\ell$, you might consider an alternative coloring $ \ell_2:V(T)\to\Sigma$ that satisfies $\ell_2(v)=\sigma$ and agrees with $\ell_1$ on $V(T)\setminus\{v\}$. Notice that necessarily $\mu(\ell_2)\leq\mu(\ell_1)$. (a key point here is that we chose $v$ to be a leaf of $T'$)
Now, we are ready for an answer (I am not claiming this is the most efficient implementation, but it doesn't look too bad).
Preparation. Let $S=\mathcal P(\Sigma)\setminus\{\emptyset\}$ the collection of nonempty subsets of $\Sigma$. Let $T$ be a tree with a partial labelling $\ell: L(T)\to\Sigma$. We associate to it the partial multilabelling $\bar\ell: L(T)\to S$ given by $\bar\ell(v)=\{\ell(v)\}$.
The algorithm. Let $T$ be a tree with a partial multilabelling $\bar\ell:L(T)\to S$. If $V(T)= L(T)$, end; otherwise, let $v\in L(T')$. For every $\sigma\in\Sigma$ count $n_v(\sigma):=\#\{w\in L_v(T):\ \sigma\in\bar\ell(w) \}$. Let $\Sigma_v = \operatorname{argmax} (n_v) \in S$ (that is, let $n(v) = \max\{n_v(\sigma):\ \sigma\in\Sigma\}$ and let $\Sigma_v:=\{\sigma\in\Sigma:\ n_v(\sigma) = n(v) \}$. 
Now, consider the subtree $\hat T =T\setminus L_v(T)$. Notice that $L(\hat T)=\{v\}\cup L(T)\setminus L_v(T)$. Consider the partial multilabelling $\hat\ell:L(\hat T)\to S$ that agrees with $\bar\ell$ on $L(T)\setminus L_v(T)$ and satisfies $\hat \ell(v)=\Sigma_v$. Iterate on $(\hat T,\hat\ell)$.
At the end, we have a tree $\tilde T$ that satisfies $V(\tilde T)=L(\tilde T)$. This happens only if $V(\tilde T)=\{v\}$ or $V(\tilde T)=\{v_1,v_2\}$. In the first case, we choose any labelling $\ell:V(\tilde T)\to\Sigma$ that satisfies $\ell(v)\in\bar\ell(v)$. In the second case, we choose $\ell:V(\tilde T)\to\Sigma$ so that $\ell(v_i)\in\bar\ell(v_i)$ for $i=1,2$, and we also make sure that $\ell(v_1)=\ell(v_2)$ in case $\bar\ell(v_1)\cap\bar\ell(v_2)\neq \emptyset$.
Returning backwards, we have a labelling $\ell:V(\hat T)\to\Sigma$ that minimizes the cost subject to the boundary multilabelling. For every $w\in L_v(T)$ we define $\ell(w)=\ell(v)$ in case $\ell(v)\in\bar\ell(w)$, otherwise we choose arbitrarily $\ell(w)\in\bar\ell(w)$. This defines an extension of the labelling to $V(T)$ that minimizes the cost, subject to the boundary multilabelling. 
Repeat until you get back to your original tree.
A: This is small parsimony problem, which is solved by Fitch's algorithm -- e.g., see http://www.cs.tau.ac.il/~rshamir/algmb/98/scribe/html/lec09/node6.html
