2
$\begingroup$

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!

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.