CO 250 Assignment 8 - Winter 2015 Due: Friday, March 20th 2015, by 4pm (sharp) Note: Submit your completed assignment to the following dropboxes outside MC 4066: Section 1 [L. Sanit`] a TTh 11:30am-12:50pm Section 2 [J. Knemann] o MWF 2:30-3:20pm Box 6, Slots 6 (A-J), 7 (K-S), 8 (T-Z) Box 7, Slots 9 (A-J), 10 (K-S), 11 (T-Z) Assignment policy: While it is acceptable to discuss the course material and the assignments, you are expected to do the assignments on your own. For example, copying or paraphrasing a solution from some fellow student or old solutions from previous oerings of related courses qualies as cheating and we will instruct the TAs to actively look for suspicious similarities and evidence of academic oenses when grading. All students found to be cheating will automatically be given a mark of 0 on the assignment (where that grade will not be ignored as the lowest assignment). In addition, there will be a 5/100 penalty to their nal mark, as well as all academic oenses will be reported to the Associate Dean for Undergraduate Studies and recorded in the student's le (this may lead to further, more severe consequences). If you have any complaints about the marking of assignments, then you should rst check your solutions against the posted solutions. After that if you see any marking error, then you should return your assignment paper to the instructor of your section within one week and with written notes on all the marking errors; please write the notes on a new sheet and attach it to your assignment paper. Please USE THE COVER SHEET that is available at the end of the assignment. It is imperative that you indicate your full name and student ID (as we have many students with the same last name). Problem 1: Feasibility of st-cut Widths The gure below shows a graph G = (V, E). Each edge e E in the gure is labelled by its length ce , and each vertex by its name. c 2 t 6 5 s 4 3 b 3 3 a (a) For each of the following vectors y, decide if it is a feasible set of cut widths. Show all your work. i) y{s} = 3, y{s,a,b} = 2, y{s,a} = 2, yU = 0 for all other st-cuts (U ). ii) y{s} = 1, y{s,b} = 2, y{s,b,c} = 1, yU = 0 for all other st-cuts (U ). iii) y{s} = 2, y{s,a} = 3, y{s,a,b,c} = 2, yU = 0 for all other st-cuts (U ). (b) Solely based on your ndings in (a), what is the best lower bound you can give on the length of the shortest st-path in G? 1 (c) Either give an st-path of length equal to the bound you provided in (b), or prove that no such st-path exists. Problem 2: A vertex cover of a graph G = (V, E) is a set S of vertices of G such that each edge of G is incident with at least one vertex of S. The following IP nds a vertex cover of minimum cardinality: xv : v V min s.t. xi + xj 1 (for all e = {ij} E) x 0, integer Denote by (P) the LP relaxation of this IP (that is, the LP obtained from the above IP after removing the integrality constraints). (a) Find the dual (D) of (P). (b) A matching in G = (V, E) is a set of edges M E such that for any two u1 v1 , u2 v2 M (u1 v1 = u2 v2 ) we have {u1 , v1 } {u2 , v2 } = . Show that the largest size (number of edges) of a matching in G is a lower bound on the size of a minimum vertex cover of G. Hint: Use part (a) and the weak duality theorem 3.2. (c) Give an example where all matchings have size strictly less than the optimal solutions of (P) and of (D) and where these are strictly less than the size of the minimum vertex cover. Problem 3: Let G = (V, E) be a graph with distinct vertices s and t and non-negative edge weights c. (a) Show that if G has no st-path then the LP max s.t. (yU : (U ) is an s, t-cut) (yU : e (U )) ce (e E) y0 is unbounded. (b) Show that the shortest path IP has an optimal solution if and only if G has an st-path. Hint: Use theorems 3.2 (Weak Duality) and 2.11 (Fundamental Theorem of LP). Problem 4: IP & Duality The county of Wellington has 7 cities, for simplicity labeled by numbers from 1 to 7. The county commissioner wants to build re stations in a subset of these cities with the following objective: each city should be reachable from a re station within 15 minutes. The graph below shows a stylized map of Wellington county. Each city corresponds to a vertex, and two cities are linked by an edge if they are connected by a road. 2 1 12 4 15 5 20 10 10 18 13 2 25 3 14 19 7 15 6 The label on each edge is the time it takes to travel between the corresponding cities. The travel time between cities s and t that are not directly connected is the length of a shortest s, t-path. The county wants to build as few re stations as possible while achieving its main objective of being close to everyone. The county hires Francesca who formulates the problem as the following IP: min (xi : 1 i 7) s.t. x1 +x2 +x4 x1 +x2 +x3 x2 +x3 +x6 x1 +x4 +x5 x4 +x5 +x7 x3 +x6 +x7 x5 +x6 +x7 1 1 1 1 1 1 1 x 0, x integer (a) Show that the above IP solves this problem. In particular, explain the denition of the variables, the role of the objective function, and the constraints. (b) State the dual of the LP relaxation of the given IP. (c) Find a feasible solution of the dual that has value strictly greater than 2. (d) Explain using the theory of duality how a correct answer to (c) implies that at least three re stations need to be built. (e) Show that it is sucient to build three re stations. Problem 5: Computing Shortest Paths For each of the following two graphs nd the shortest path between s and t using the algorithm described in class. In the gures below, each edge is labeled by its length. Make sure to describe for each step of the algorithm which edge becomes an arc, which vertex is added to the set U and which st-cut is assigned a positive width. At the end of the procedure give the shortest st-path and certify that it is indeed a 3 shortest st-path by exhibiting feasible widths. 2 2 4 2 3 6 3 3 3 s 4 2 4 4 3 1 6 1 t 1 s 5 7 3 7 2 1 4 t CO 250 ASSIGNMENT 8 - COVER SHEET Surname: First Name: Signature: Id.#: Section#: Problem 1 Mark Awarded 2 3 4 5 Total 5