0
$\begingroup$

There are N nodes in a graph and some of them are connected with edges. All nodes are of type T1. The goal is to update all nodes to type T2. At any step you can choose any set of nodes and change their type to type T2 with the only restrictions that no nodes in the chosen set can be connected with an edge (i.e. this sub-graph should not have edges). Find the minimum number of steps required to update all nodes to type T2.

A graph can have any topology, i.e. nodes can be connected in a random fashion without any pattern

$\endgroup$
  • $\begingroup$ What have you tried? Where did you get stuck? We want to help you with your specific problems, not just do your exercise for you. However, as it is we don't know what this problem is and thus how to help. See here for a relevant discussion. $\endgroup$ – D.W. Feb 15 '15 at 21:24
1
$\begingroup$

Hint: Your question is tantamount to finding a partition of the vertices of the graph into as few independent sets as possible. This is the same as finding the chromatic number of the graph, which is NP-complete.

$\endgroup$

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.