Homework 7 (assigned February 20, due February 27)

Reading: CLRS chapter 29, Matousek & Gartner, chapters 5–6.

Written assignment: Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in.

"Do" Exercises (not to be handed in):

1. Exercise 34.5-3, page 1101.

2. Problem 29-3, page 895.

3. The 3-COLORING problem is as follows:
   Input: an undirected graph G = (V, E)
   Output: a valid 3-coloring c: V → {Red, Green, Blue}, or report that none exists
   The 4-COLORING problem is as follows:
   Input: an undirected graph G = (V, E)
   Output: a valid 4-coloring c: V → {Red, Green, Blue, Yellow}, or report that none exists
   Recall that c is a valid coloring if c(u) ≠ c(v) for every edge (u, v) ∈ E.
   • Find a reduction from 3-COLORING to 4-COLORING.
   • Use this reduction to prove that if there is a polynomial-time algorithm for the 4-COLORING problem, then there is a polynomial-time algorithm for the 3-COLORING problem.

Problems (to be handed in):

1. Formulate the HAMILTON CYCLE problem as an integer linear-programming problem. (5 points)

2. Consider the following simple two-player game. The players Alice and Bob each choose an outcome, heads or tails. If both outcomes are equal, Bob gives $1 to Alice; if the outcomes are different, Alice gives $1 to Bob.
   • Represent the payoffs by a 2 × 2 matrix. (2 points)
   • What is the value of this game, and what are the optimal strategies for the two players? (3 points)

3. Find the value of the game specified by the following playoff matrix. (5 points)
   

4. Formulate the change-making problem as an integer linear-programming problem. The input to the change-making problem is a positive integer A, the amount we want to make change for, and positive integers x₁, x₂, …, x_n, the coin denominations. (5 points)
   Can we solve this program as an LP, in the certainty that the solution will turn out to be integral? Either prove it or give a counterexample. (2 points)

5. Write a linear program for solving the minimum Vertex Cover problem in bipartite graphs. The input is a bipartite graph G = (X ∪ Y, E), where E ⊆ X × Y. Your linear program should have one variable for each vertex. Prove/argue that the value of your linear program is at most the minimum vertex cover size. (10 points)
   Write the dual to the linear program for the minimum vertex cover problem in bipartite graphs. What problem does this linear program represent? (5 points)

6. Consider the two-player game with players, strategies, and payoffs described in the following game matrices.
        
   • Argue that in an optimal strategy Player 1 should not follow strategy A. (2 points)
   • Find a similar column for Player 2. Simplify the game by eliminating these strategies. (2 points)
   • Consider the resulting 2 × 2 matrices. Conclude that there is a best strategy for Player 1 and a best strategy for Player 2. Find it and find the payoffs. (3 points)
   • Verify that this pair of strategies was a Nash equilibrium for the original game. (3 points)

7. Consider two criminals accused of robbery. They can Confess or Deny with the following payoff matrices.
        

   Argue that C, C is the only Nash equilibrium in the game. (5 points)

8. The k-SPANNING TREE problem is the following:
   Input: an undirected graph G = (V, E)
   Output: a spanning tree of G in which each vertex has degree ≤ k, or report that none exists
   Show that for any k ≥ 2:
   • k-SPANNING TREE is in NP, i.e., you must show how to verify in polynomial time whether a candidate graph is a k spanning tree or not. (2 points)
   • k-SPANNING TREE is NP-complete, i.e., you must exhibit a reduction from a known NP-complete problem A to the k-SPANNING TREE problem, and use this reduction to prove that if there is a polynomial-time algorithm for the k-SPANNING TREE problem, then there is a polynomial-time algorithm for problem A also. (6 points)