MS&E 217/317, Combinatorial Optimization, Autumn 2003-04.Instructor: Ashish Goel
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 6th 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 Hj = 1 + 1/2 + 1/3 + 1/4 + Ö 1/j is O(log j).
(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 Ai,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 GC, where the complement graph GC 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?