Consider the following problem. The input consists of a directed graph G with a specified source vertex s, and a positive integer profit for each vertex of G. The objective is to find a subset H of the vertices of maximum total profit subject to the constraint that there is a collection of vertex disjoint paths from s to the vertices in H. That is, if H = {v1, ..., vk} there there must be paths P1, . . . , Pk such that each path Pi starts at s and ends at vi , and no pair of paths share a vertex other than s.

(a) Write an integer linear programming formulation for this problem Hint: As is usually the case, the key is to figure out what the variables will be. Probably the most natural formulation has two types of variables.

(b) Consider the relaxed linear program where the integrality requirements are dropped. Explain how to find an integer optimal solution from any rational optimal solution. Hint: Morally this rounding is the same as for matching, but the implementation is a bit more complicated.

(c) Give a strongly polynomial time algorithm for this problem (note that no one knows of a strongly polynomial time algorithm for linear programming). You must prove your algorithm is both correct, and runs in strongly polynomial time.