MS&E 217/317, Combinatorial Optimization, Autumn 2003-04.Instructor: Ashish Goel

Handout 13

Practice Problems for the finals, for material not covered by the HWs.

I will not be able to give out solutions to these problems. However, I will post brief hints on Friday. Also, if anyone submits their solutions by Sat Dec 6^th evening (by slipping them under my door), I will return them with comments on Monday afternoon during my office hours.

1. Stable Marriages: We will do a probabilistic analysis of the algorithm of Gale and Shapley. Suppose that each man ranks all the women in a completely random order, independent of all other men.

(a) Suppose there are k women who have not yet been proposed to. Then there must be k unengaged men. Prove that the probability that the next proposal goes to an unengaged woman is at least k/n.

(b) Use (a) to prove that the expected number of proposals before one more woman becomes engaged is at most n/k.

(c) Now argue that the expected total number of proposals before the algorithm terminates is O(n log n). Use the fact that the j-th Harmonic number H_j = 1 + 1/2 + 1/3 + 1/4 + … 1/j is O(log j).

2. Matchings.

(a) A maximal matching M’ in a graph is a matching whose size cannot be increased by simply adding an additional edge. If M is a maximum matching, then prove that |M| <= 2|M’|.

(b) Prove that there always exists a series of augmentations such that Edmond’s algorithm does not encounter any blossoms.

(c) Prove that if a graph does have odd circuits, there always exists a series of possible actions in Edmond’s algorithm that will result in the detection and contraction of a blossom.

(d) [317 only] The permanent of an n X n matrix A, denoted Per(A), is . Here S(n) is the set of all permutations of n numbers. Informally, the permanent is like the determinant, but without the sign inversions. In fact, the permanent is incredibly hard to compute – it is believed to not even be in NP. Consider an undirected bipartite graph G = (V,E) with each partition being of size n. Let A_i,j = 1 if (i,j) is in E, and 0 otherwise. Establish a connection between Per(A) and the number of perfect matchings in G. Give a polynomial time algorithm to compute whether Per(A) is non-zero.

(e) [317 only] Show by example that if G = (V,E) is a graph, M is a matching of G, and b a blossom, then the following may fail to be true: There is an M-augmenting path in G iff there is an (M/b)-augmenting path in G/b. Why does this not contradict the theorem we stated in class which formed the basis of blossom shrinking in Edmond’s algorithm?

(f) The bottleneck matching problem is the following: Given a graph G=(V,E) and a weight w defined on the edges, find a perfect matching M (if one exists) such that the maximum weight of an edge in M is minimized. Hint: Use binary search on top of Edmond’s algorithm.

3. NP completeness and approximation algorithms.

(a) Prove that König’s lemma does not hold for non-bopartite graphs.

(b) Prove that if C is the smallest vertex cover of a graph, M is a maximum matching, and M’ is a maximal matching, then |M’| |M| |C| 2|M’|. Use this fact, along with a simple algorithm for maximal matchings, to obtain a polynomial time 2-approximation for the optimization version of the VERTEX-COVER problem (i.e. finding a minimum vertex cover). It is desirable, but not necessary, that your algorithm run in time O(m+n).

(c) A subset S of V is said to be a clique in G=(V,E) if every pair of nodes in S is connected by an edge. The decision problem CLIQUE takes an input of (G,k). The answer is YES if G has a clique of size at least k and NO otherwise. Prove that CLIQUE is NP-complete. Hint: Use a reduction from Vertex-Cover. Further hint: What is the relation between a clique in G and a vertex cover in G^C, where the complement graph G^C has the same vertices as G but a complementary set of edges?

(d) [317 only] The optimization version of the CLIQUE problem is to find a largest clique in G. What does the 2-approximation for VERTEX-COVER imply for the CLIQUE problem in terms of its approximability?