Fall 22: CSci 5421—Advanced Algorithms and Data Structures Homework 4
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Fall 22: CSci 5421—Advanced Algorithms and Data Structures
Homework 4
1. (12 points) Let S be a finite set and let Sl, S2 , . . . , Sk be a partition of S, i.e., the sets Si are pairwise-disjoint and their union is S .
Let I = {A : A S S and |A n Si| s 1, for 1 s i s k}. In other words, A contains at most one element from each Si .
Prove that M = (S, I) is a matroid by showing that the hereditary and exchange properties hold. Give a careful proof of each.
Example: Let S = {a, b, c, d}. Then Sl = {a}, S2 = {b, d}, and S3 = {c} is a partition of S . We have A = {a, b} e I. However, A = {a, b, d} /e I.
(Your proof must be general and not based on just this example.)
2. (12 points) Recall the statement of the OSP for weighted matroid optimization, as discussed in class (see the lecture slides). We defined there a set system M\ = (S\ , I\ ), based on a matroid M = (S, I). (Ignore the weight function.)
Prove that M\ is a matroid by showing that the hereditary and exchange properties hold. Give a careful proof of each. (In your proof, you should use the fact that M is a matroid.)
Note: Use the definition of M\ given in the lecture slides; this is slightly different from the one in the text.
3. (9 points) Consider the 2-approximation algorithm in Section 35.1 for finding a vertex cover in an undirected graph G. (Also discussed in class.) Prove that the set of edges selected by the algorithm forms a maximal matching in G.
Recall that a matching in a graph is a set of edges where no two share an endpoint. A matching is maximal if it is not contained properly in any other matching.
4. (11 points) Let G = (V, E) be an undirected graph. A clique in G is a subset of V where every pair of vertices in the subset is connected by an edge of E .
(a) Prove that S is a clique of G if and only if S\ = V - S is a vertex cover of G\ = (V, E\ ), where
E\ = {(u, v) : u, v e V and (u, v) e\ E}. Give a careful proof.
Finding a clique of maximum size is computationally hard (the corresponding decision prob- lem is NP-complete). However, the result in part (a) suggests a possible approach to a polynomial-time approximation algorithm for maximum clique: Given G, compute G\ and run the 2-approximate vertex cover algorithm on G\ . Let C be the vertex cover found. Re- turn V - C as an approximate maximum clique.
(b) Give an example of a graph G on n vertices for which the size of a maximum clique is cn,
for some positive constant c s 1, but for which the algorithm above returns a clique of size Θ(1). You must establish these bounds for your graph. (This shows that the algorithm above can be arbitrarily bad in its approximation, despite vertex cover having a constant-factor approximation algorithm.)
5. (13 points) Let G = (V, E, w) be a complete, undirected, edge-weighted graph, where |V | = n and the edge weights w(.) satisfy the triangle inequality. Consider the following heuristic to find an approximate traveling salesperson tour in G.
Pick any vertex and consider this to be a trivial cycle, Cl, consisting of one vertex. In a general step, let Ci be the cycle constructed so far on i vertices, 1 s i < n. Compute Ci＋l as follows:
Find an edge (x, y) in G of minimum cost, where x e\ Ci and y e Ci (ties broken arbitrarily). Let z be a neighbor of y on Ci, i.e., z is a vertex on C that is adjacent to y . Replace the edge (y, z) on Ci by the edges (x, y) and (x, z) to obtain Ci＋l . (When i = 1, y and z are the same vertex, so C2 is just two copies of the edge (x, y).) Return Cn as the approximate tour.
Let C大 be the minimum length tour. Prove that w(Cn)/w(C大 ) s 2. (With a slight abuse of notation, we use w(Cn) and w(C大 ) to denote the lengths of Cn and C大 , respectively.)
Hint:
(i) Use the triangle inequality to obtain an upper bound on w(Ci＋l) - w(Ci) in terms of w((x, y)). (ii) Argue briefly (but clearly) that the edges (x, y) found during the n - 1 iterations above form a minimum spanning tree.
(iii) Use (i) and (ii) to obtain the desired upper bound on w(Cn)/w(C大 ).
2022-11-15