Name:

67.612 Combinatorial Optimization and Integer Programming, Spring 91.

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₁,W₂) being a bipartition of V. Assume $\mid W_1\mid =\mid W_2\mid =n$. Show that G has a matching of cardinality n if

$$\mid \{ \mbox{neighbours of } S \} \mid = \mid \{u\in W_2:... ...\in E \mbox{ for some } v \in S \}\mid \; \geq \; \mid S\mid$$

for all $S \subseteq W_1$.

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 $\max\{c^Tx : Ax \leq b, x \geq 0, x \mbox{ integer} \}$.

(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 $\max\{c^Tx : Ax \leq b, x \geq 0 \}$ is $\min\{b^Ty : A^Ty \geq c, y \geq 0 \}$.)

4.

(15 points) Let G=(V,E) be a graph with weights w_e on the edges. Assume $w_{e_i}\neq w_{e_j}$ 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 $V\setminus U$. Show that T must contain the shortest edge between U and $V\setminus U$.

5.

(25 points. Each part is worth five points.) Give short justifications for your answers.

(a)

An instance d of a feasibility problem $X \in NP$ depends upon two positive integer parameters m and n. Assume d requires storage m2ⁿ 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 $m\leq n$ 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?