Name: |

Midterm Exam, Tuesday, March 5, 1991.

Please do all five problems. Show all work. No books or calculators allowed. You may use any result from class, the homeworks, or the texts.

Q1 | ||

Q2 | ||

Q3 | ||

Q4 | ||

Q5 | ||

Total |

- 1.
- (20 points)
Let
*G*=(*V*,*E*) be a bipartite graph with (*W*_{1},*W*_{2}) being a bipartition of*V*. Assume . Show that*G*has a matching of cardinality*n*if

for all . - 2.
- (15 points) Show that the graph feasibility problem
Is

is in both*G*bipartite?*NP*and*CoNP*. - 3.
- (25 points) Consider the graph

- (a)
- (5 points) Give a maximum cardinality matching for this graph.
- (b)
- (5 points) Formulate the problem of finding the maximum cardinality matching in the form .
- (c)
- (5 points) Give an optimal solution to the linear programming relaxation of the integer program given in part 3b.
- (d)
- (5 points) Suggest an additional constraint for the LP relaxation.
- (e)
- (5 points) Formulate and solve the dual of the LP relaxation with the additional constraint. (The dual of the problem is .)

- 4.
- (15 points) Let
*G*=(*V*,*E*) be a graph with weights*w*_{e}on the edges. Assume for any pair of edges*e*_{i}and*e*_{j}. Let*T*be a minimum weight spanning tree on this graph. Divide the vertices into two sets*U*and . Show that*T*must contain the shortest edge between*U*and . - 5.
- (25 points. Each part is worth five points.)
Give short justifications for your answers.
- (a)
- An instance
*d*of a feasibility problem depends upon two positive integer parameters*m*and*n*. Assume*d*requires storage*m*2^{n}in binary, and that we know an algorithm*A*which solves*d*in time 2^{m+n}.- i.
- Can we conclude
*X*is in*P*?

- ii.
- Can we conclude
*X*is not in*P*?

- iii.
- Assume we know in addition that
for every
instance
*d*of*X*. What can we conclude now?

- (b)
- i.
- Is the given (
*s*,*t*) flow optimal? (The numbers on the arcs indicate the capacity and the flow.)

- ii.
- Is the given matching optimal?

John E. Mitchell