67.612 Integer Programming and Combinatorial Optimization

Thursday, March 16, 1989. 2 hours.

Answer all questions.

1.

(20 points.) Find the minimum weight spanning tree in the graph below. Specify the algorithm you use and the order in which you construct your tree.

2.

(15 points.) Consider using the Bellman-Ford algorithm to find the shortest path from s to t in a graph with edge lengths as follows:

				TO
		s	1	2	3	4	t
	s	--	3	2	100	100	100
	1	100	--	-2	3	100	100
FROM	2	100	4	--	2	6	100
	3	100	100	100	--	3	-4
	4	100	100	-4	100	--	-8
	t	100	100	100	100	100	--

(So, for example, the length of the arc from node s to node 2 is 2. `--' indicates the corresponding edge does not exist.)

Let a_i^k be the length of the shortest path from s to i which uses at most k edges. How would you calculate a_i^k+1?

We find a_s³=0, a₁³=3, a₂³=1, a₃³=3, a₄³=7, and a_t³=0. What are a_i⁴, i=s,1,2,3,4,t?

3.

(20 points.) Consider the problem of finding the maximum cardinality matching in a bipartite graph.

(a)

Express this problem as a linear programming problem P.

(b)

What is the dual linear program D to P?

(c)

How do node covers relate to feasible solutions to D?

(d)

What are the complementary slackness conditions for the dual pair of linear programming problems D and P?

4.

(30 points.) Let T be a finite set. Let $S_i\subseteq{T}$, $i=1,2,\ldots,m$, and let $\Sigma=\{S_1,S_2,\ldots,S_m\}$. A list $(f_1,f_2,\ldots,f_m)$ of distinct elements of T which satisfy $f_i{\in}S_i,i=1,\ldots,m$ is called a system of distinct representatives (SDR) of $\Sigma$.

For example:

Let T={a,b,c,d,e}.

If $\Sigma=\{\{a,b,c\},\{a,d,e\},\{a,d,e\},\{a,e\}\}$ then (c,d,e,a) is an SDR for $\Sigma$.

However, if $\Sigma=\{\{a,b,c\},\{a,d,e\},\{a,d,e\},\{a,e\},\{d,e\}\}$ then there does not exist an SDR for $\Sigma$.

(a)

Show that if there exists an SDR for $\Sigma$ then every ${\Sigma}'=\{S_{i_1},\ldots,S_{i_k}\}\subseteq\Sigma$ must contain at least k distinct elements of T, ie, the cardinality of ${\cup}_{j=1}^k S_{i_j}$ is greater than or equal to k.

(b)

Use the max-flow/min-cut theorem to show that if every ${\Sigma}'=\{S_{i_1},\ldots,S_{i_k}\}\subseteq\Sigma$ contains at least k distinct elements of T then there exists an SDR of $\Sigma$. (Hint: Construct a bipartite graph with bipartition (W₁,W₂). Let the elements of W₁ correspond to the elements of T. Let the elements of W₂ correspond to the elements of $\Sigma$. Show that if there exists a flow of size m then there exists an SDR. What can you conclude about the value of the maximum flow if there does not exist an SDR? If there exists a cut of size less than m, consider the elements of W₂ that are not reachable from s with respect to the optimal flow.)

    

5.

(15 points.) For each of the questions below, answer either yes or no and give a short justification for your answer.

(a)

Is the flow in the following graph maximum? (The pair of numbers on each edge e is (x(e),c(e)), where x(e) is the flow on edge e and c(e) is the capacity of edge e.)

(b)

Is the node cover in the following graph minimum?

(c)

Is the matching in the following graph maximum? (Squiggly lines indicate matched edges.)