Instructions:

Typically, the clearest way to explain an algorithm is in English, with the use of some notation. A clear explanation followed by annotated pseudo-code is also fine.

Remember that when a problem asks you to design an algorithm, you must also prove the algorithms correctness and analyze its running time, i.e., the running time must be bounded by a polynomial function of the input size. (Include Proof)

(2) (10 points) Given an undirected graph G=(V,E) with vertex-weights cv for vV and edgeweights ce for eE, define a valid coloring of the vertices vV and edges eE to red or blue if it satisfies the following property: for every vertex vV that is colored red, there is a vertex wV which is colored blue, and there is a path P from v to w using only blue edges. Design an algorithm that takes as input G=(V,E) with vertex-weights cv for vV and edgeweights ce for eE, and outputs such a valid coloring that minimizes the total weight of nodes and edges that colored blue, i.e., minimizes the quantity vV:viscoloredbluecv+eE:eiscoloredbluece