1. A vertex v in an undirected graph G is an odd cycle transversal if every cycle of odd length in G contains the vertex v. Develop a linear-time algorithm for the following problem: given a graph G and a vertex v in G, decide if v is an odd cycle transversal.
2. Suppose that each class Ci has an enrollment ri while each classroom Rj has a capacity cj. A classroom Rj is “feasible” for a class Ci if cj/2 ≤ ri ≤ cj. Develop an efficient algorithm that, on a set of classes (with enrollments given) and a set of classrooms (with capacities given), make a feasible assignment of the classes to the classrooms such that the as many classes as possible can get held starting at
3.Suppose that in addition to edge capacities, a flow network also has vertex capacities, i.e., each vertex v has a limit c(v) on how much flow can pass through v. Show how to transform a flow network G = (V,E) with vertex capacities into a flow network G0 = (V 0,E0) without vertex capacities, such that a maximum flow in G0 has the same value as a maximum flow in G.
4. (Textbook, page 731, Question 26.2-10) Show how to find a maximum flow in a flow network G = (V,E) by a sequence of at |E| augmenting paths. (Hint: determine the paths after finding the maximum flow.)
