0
$\begingroup$

Assume that a tree $T$ is given and we want to assign a color to each vertex of it. The color should be red or blue and no adjacent vertices can have color blue. (They can both be red but not blue)

Provide a linear time algorithm to assign colors (red or blue) to the vertices of $T$ in a way that the number of blue vertices are maximized.

Any idea? I'm completely stuck... I don't know a way to start! it doesn't just want a simple coloring. It should be a coloring with maximizes the number of blue vertices. That's the entire point. How can we be sure that this condition is satisfied?

Hint: Think of the dynamic programming approach.

$\endgroup$
  • $\begingroup$ Do you have any restriction on coloring? May be adjacent vertices should have different colors? $\endgroup$ – Smylic May 19 '17 at 14:48
  • $\begingroup$ @Smylic Yes... i forgot to write it... i'll make an edit $\endgroup$ – Arman Malekzadeh May 19 '17 at 14:51
  • $\begingroup$ @Smylic the condition is a bit different... see the question again :) $\endgroup$ – Arman Malekzadeh May 19 '17 at 15:08
0
$\begingroup$

This part is about proper colorings. Any tree is connected bipartite graph. So when you color one vertex you can use either breadth-first search or depth-first search to color all other vertices, because when you push new vertex to a queue or stack you know the only appropriate color for it. Since you have only two possibilities to color the first vertex the time is linear, no DP is required.


This part is about maximum independent set. So after edit question become about maximum independent set (the set of blue vertices). For leave $v$ it is easy to see that there is maximum independent set $I_v$ that contains $v$. Really if some maximum independent set $I'$ doesn't contain $v$ than it should contain the only neighbor $u$ of $v$ because otherwise it is not maximal and therefore can not be maximum. Then $I_v = (I' \setminus \{\,u\,\}) \cup \{\,v\,\}$. Also if $\deg v = 0$ then $v$ obviously should be in each maximum independent set.

Therefore the algorithm is the following. Take arbitrary vertex of degree 0 or 1 leave color it into blue and remove this vertex from graph together with its neighbor if it exists. Continue while there are non-colored vertices. To make this approach efficient we can use queue (or stack) which contains all non-colored vertices of degree 0 or 1. Still no DP is required.

If DP is the only acceptable way then let's do the following. Do depth-first search (so the stack is required anyway). For each vertex $v$ compute the number of blue vertices in subtree of $v$ if $v$ is blue (number $f_b(v)$) and if $v$ is red (number $f_r(v)$). It is possible to compute it after computing for all children in the following way: $$f_b(v) = 1 + \sum_{u \in N^+(v)} f_r(u),\\ f_r(v) = \sum_{u \in N^+(v)} \max\{\,f_r(u), f_b(u)\,\}.$$ This way also gives linear time.

$\endgroup$
  • $\begingroup$ Though you probably want $f_r(v) = \sum_u \max\{f_r(u), f_b(u)\}$, instead. $\endgroup$ – Misha Lavrov May 19 '17 at 17:32
  • $\begingroup$ Yes, you are right. Thank you! $\endgroup$ – Smylic May 20 '17 at 6:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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