Due: Thursday, February 18, 2021, by end of day.
Penalty for late homeworks: 10% for each day or part of a day.

1. A method for representing a spanning tree on the complete graph on vertices {1,,n} as a string of n - 2 numbers was presented in class. Find the trees with 8 vertices corresponding to the following strings:
1. 543156.
2. 768773.
3. 543854.
2. Show that Which formulation do you think is most effective for solving max{cTx : x S}? Why? How do the feasible regions of the LP relaxations compare?
3. Model the following feasibility problem as an integer programming feasibility problem:

Given a graph G = (V,E), does there exist a partition of the edges E into two sets E1 and E2 such that neither E1 nor E2 contains a triangle?

Is the LP relaxation to your formulation feasible?

4. Assume you have an algorithm A for finding the minimum weight perfect matching in a graph with nonnegative edge weights. How could you use this algorithm to find the maximum weight matching in a graph G = (V,E) with nonnegative edge weights? (Note: the matching isn’t required to be perfect.)
5. Assume we have a polynomial time algorithm for determining the optimal value of binary knapsack problems of the form max{cTx : x Bn,aTx b}. This algorithm does not tell us the values of the variables in the optimal solution. Show that we can use this algorithm as a subroutine in a polynomial time algorithm for finding the optimal solution to a binary knapsack problem.
 John Mitchell Amos Eaton 325 x6915. mitchj at rpi dot edu Office hours: Monday and Thursday 1pm–2pm. webex: https://rensselaer.webex.com/meet/mitchj