princeton university F’08 cos 521: Advanced AlgorithmsHomework 3Out: Nov19 Due: Dec 1You can collaborate with your classmates, but be sure to list your collaborators with youranswer. If you get help from a published source (book, paper etc.), cite that. Also, limityour answers to one page or less —you just need to give enough detail to convince me. Ifyou suspect a problem is open, just say so and give reasons for your suspicion.§1 A cycle cover of a graph (directed or undirected) is a collection of cycles such thatevery vertex is in exactly one cycle. Describe a polynomial-time algorithm to decidewhether or not a cycle cover exists.§2 Suppose we wish to solve the following flow problem. There are n nodes in an undi-rected graph, and the edges should be thought of as pipes of a certain capacity. Foreach pair {i, j} we wish to send 1 unit of fluid between them. All these flows must berouted through the pipes and should not violate any capacity. Let z be the minimumnumber such that if all edge pipes have capacity z then the flows can be routed in thenetwork. Express the problem of finding z as a linear program, and argue that it canbe solved in polynomial time.§3 Use the multiplicative weights method to design a algorithm that solves the abovelinear program approximately. How long does your algorithm take to find z correctlyup to an additive error  > 0?§4 For a 5-regular undirected graph G = (V, E) we define the conductance Φ(G) to be:minS⊆VE(S, S)|S| ·S.(a) Show that the diameter of the graph is O(log n/nΦ(G)). (Hint: Consider doinga breadth first search from any point. How many levels does it take to doublethe number of nodes that are in the BFS tree?)(b) Show that if zOP Tis the optimum value of LP in the previous question thenzOP T≥ 1/Φ(G).(c) Show that the dual of the LP in the previous question is equivalent to the follow-ing problem. We assign a nonnegative weights weto each edge e. This inducesa distance function among the vertices, and we let dijbe the distance betweeni, j. We have to minimize the sum of the we’s while keepingPi<jdij= 1.(d) Show that zOP T≤ O(log n/Φ(G)). (Hint: Consider the weighted graph definedby the dual weights we. Replace edge e with a sequence of unweighted edges andconsider the conductance of this graph. You have to do other things too.)12§5 Let L be the normalized Laplacian of a graph, namely the matrix whose diagonalentries are 1 and the offdiagonal entry (i, j) is −1/pdidj. Show that this matrix ispositive semidefinite, has all its eigenvalues between 0 and 2, and the second eigenvalueis the minimum over all x ∈ <nsatisfyingPidixi= 0 of the following expression:P{i,j}∈E(xi− xj)2Pidix2i.Show that if the graph is 5-regular then second eigenvalue is upper bounded byO(nΦ(G)).§6 In class we defined zero-sum two-person games, which are given by a single payoffmatrix A. Now consider a game specified by two matrices A, B that are n × m. Ifplayer 1 makes move i ∈ {1, . . . , n} and player 2 makes a move j ∈ {1, . . . , m} thenplayer 1 wins Aijand player 2 wins Bij. (The zero-sum game is a special case whereA = −B.) Show that there exist two mixed strategies p1, p2for the two players suchthat each is a profit maximizing response to the other. (This pair of strategies iscalled a Nash equilibrium, the discovery for which John Nash won a Nobel prize ineconomics.)You can use Brouwer’s fixed theorem, which says that if S is a convex compact set in<nand f is a continuous function from S to S then f has a fixed point, namely, somex ∈ S such that f(x) = x.§7 In the ultimatum game Kid 1 is asked to share 4 cupcakes with Kid 2. Kid 1 has tosuggest a nonzero and integral amount x he is are willing to give to the other. Kid 2has to suggest a minimum amount y he is willing to accept. If x ≥ y then Kid 1 givesx cupcakes to Kid 2. If x < y then neither gets anything.Write matrices A, B for this game and compute a Nash Equilibrium. Is the equilibriumunique? If not, can you compute another?§8 Write an SDP relaxation for the MAX-2SAT problem. Use a Goemans-Williamsontype rounding algorithm to achieve an approximation ratio better than the 3/4 weachieved in class using an LP relaxation. Improve it as much as you