I am trying to solve the following problem :
For a tree $T = (V, E)$, where $V$ is the set of vertices and $E$ is the set of edges. A label $L$ of $T$ is an application from $T$ to $\{0,1\}^{|V|}$. For a given label $L$ and a given $e = \{u,v\} \in E$, the weight $w_e$ of $e$ is defined as $$w_e = \left\{\begin{array}{cc}1 & \text{if $L(v) \neq L(u)$} \\ 0 & \text{if $L(v) = L(u)$}\end{array}\right.$$ Let $\mathcal L(T)$ be the set of leaves of $T$ (ie $\mathcal L(T) = \left\{v \in V \,:\, |\{e \in E \,:\, v \in e\}| = 1\right\}$).
Given an application $M : \mathcal L(T) \to \{0,1\}^{\mathcal L(T)}$ wich is a label on the set of leaves of $T$, how can we construct a label $L$ of $T$ that minimizes the total weight and such that for every $v \in \mathcal L(T)$ $L(v) = M(v)$.
I can formulate the problem by integer program. Indeed, the input is $T = (V, E)$ and two disjoints sets $\mathcal L^1$ and $\mathcal L^0$ such as $\mathcal L(T) = \mathcal L^1 \cup \mathcal L^0$ (the leaves in set $\mathcal L^i$ are labeled with $i$, for $i=0,1$). The following integer program is a formulation of the problem $$\begin{array}{crcl}\underset{\substack{z \in \{0,1\}^{|V|} \\ x \in \{0,1\}^{|E|}}}\min & \displaystyle\sum_{e\in E} x_e \\ & x_{\{u,v\}} - z_u + z_v &\ge& 0 & \forall \{u,v\} \in E \\ & z_v &=& 1 & \forall v \in \mathcal L^1 \\ & z_v &=& 0 &\forall v \in \mathcal L^0 \end{array} $$
But I can not obtain a polynomial algorithm to solve this problem. Can anyone help me to find a polynomial algorithm for solving this problem or some heuristic that gives a good approximation of it.
A binary vertex labelling whose restriction on the set of leaves $\mathcal L(T)$ coincides with a given labelling $M$ of leaves we shall call admissible. If all vertices of $T$ are leaves, then there is nothing to solve, so we assume that there exists a vertex $v_0$ of $T$ which is not a leaf. Fix it as a root of $T$. Now for each vertex $v$ of $T$ let $T_v$ be a subtree of $T$ rooted at $v$. We recursively calculate $w_0(v)$ and $w_1(v)$, where $w_i(v)$ is the minimum total weight of edges of $T_v$ taken over all admissible labellings $L$ of $T$ such that $L(v)=i$. It is easy to see that for each $v\in V$ and $i=1,2$ we have $$w_i(v)=\sum \{\min\{w_i(u),1+w_{1-i}(u)\}: u\mbox{ is a child of }v\}.$$ The minimum total edge weight which we are looking for is $\min\{w_0(v_0), w_1(v_0)\}$ and is calculated in $O(E)=O(V)$ time.
Added. Given an admissible labelling $L$ of $T$ and a vertex $v$ of $T$ let $w(v,L)$ be the total weight of edges of $T_v$.
When we label $v_0$ by $\operatorname{argmin}\{w_i(v_0)\}$, the recursive formula will guide us to label its children and so forth, finally building a labelling $L$ such that $w(v,L)=w_{L(v)}(v)$ for each non-root vertex $v$ of $T$. The minimality of $L$ follows from the definition of $w_i(v)$, which is the minimum total weight etc., so it remains to explain the recursive formula for $w_i(v)$. Let $L’$ be any admissible labelling of $T$. We recursively show that $w(v, L’)\ge w_{L’(v)}(v)$ for each vertex $v$ of $T$. If $v$ is a leaf then $w_{L’(v)}(v)=w(v, L’)=0$. Otherwise by the recursion hypothesis,
$$w’(v, L’)=\sum \{w(u, L’): u\mbox{ is a child of }v\mbox{ and }L’(u)=L’(v)\}+ \sum \{w(u, L’)+1: u\mbox{ is a child of }v\mbox { and }L’(u)\ne ‘L(v)\}\ge \sum \{w_{L’(u)}(u): u\mbox{ is a child of }v\mbox { and }L’(u)=L’(v)\}+$$ $$ \sum \{w_{L’(u)}(u)+1: u\mbox{ is a child of }v\mbox { and }L’(u)\ne L’(v)\}\ge$$ $$ \sum \{\min\{w_{L’(v)}(u),1+w_{1-L’(v)}(u) \}: u\mbox{ is a child of }v\mbox { and }L’(u)=L’(v)\}+\sum \{\min\{1+w_{1-L’(v)}(u), w_{L’(v)}(u)\}: u\mbox{ is a child of }v\mbox { and }L’(u)\ne L’(v)\}=\sum \{\min\{w_{L’(v)}(u),1+w_{1-L’(v)}(u) \}: u\mbox{ is a child of }v\}=w_{L’(v)}(v).$$