Consider an undirected graph G with vertices V and edges E. For each edge (u,v) in E, we have a weight w(u,v) specifying the cost to connect vertices u and v. We then wish to find an acyclic subset T E that connects all of the vertices and whose total weight, w(T) = the sum of w(u,v) for all (u,v) T, is minimized. This is called the minimum-spanning tree problem. Consider the minimum spanning-tree problem for all parts below.

(a) Give an integer linear programming formulation using the following intuition, and prove that your formulation is correct: There is an indicator 0/1 random variable for each edge. You must choose at least n 1 edges (n is the number of vertices in the graph). For each subset S of k vertices, you can choose at most k 1 edges connecting vertices in S. Explain why the size of this linear program can be exponential in the size of the graph.

(b) Give an integer linear programming formulation using the following intuition, and prove that your formulation is correct: There is an indicator 0/1 random variable for each edge. You must choose at exactly n 1 edges. For each subset S of vertices (S not the empty set and not all the vertices), you must choose at least one edge with one endpoint in S and one endpoint not in S. Explain why the size of this linear program can be exponential in the size of the graph. HINT: Theorem 23.1 in the text (Introduction to Algorithms 3rd edition) may be useful.

(c) Give a polynomial sized integer linear programming formulation using the following intuition, and prove that your formulation is correct: Call an arbitrary vertex the root r. Think of a spanning tree as routing flow away from r to the rest of the tree (but now you do not have flow conservation at the vertices). Explain why the size of this linear program is polynomially bounded in the size of the graph.

(d) Consider a relaxation of the integer linear program in the last subproblem in that now the flows on the edges may be rational (and not necessarily integer). Show how to express an optimal rational solution to the linear program as an affine combination of optimal (rooted) spanning trees. Conclude that one can compute in polynomial time an optimal spanning given the optimal rational solution to this linear program HINT: The coefficient for the first tree will be the least flow on any edge. And then repeat this idea.