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 (W1,W2) 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 G bipartite?
is in both 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 we on the edges. Assume for any pair of edges ei and ej. 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 m2n in binary, and that we know an algorithm A which solves d in time 2m+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
2005-12-09