Please submit the assignment on Crowdmark by the due date.  In all problems below where you are asked to give an efficient algorithm, you must also prove that your algorithm is correct and analyze its running time. If you use any sources other than the course textbook or the lecture notes (e.g. other textbooks, online notes, friends) please cite them for your own safety. Do not upload this assignment to any online repository. Also, a reminder that direct copying from sources is not permitted, and solutions must be in your own words.

Questionsc

1. A k-star is the graph on k + 1 vertices u, v1 , v2 , . . . , vk  with edgesuv i  for each i ∈ [k]. A graph G = (V, E) is k-star free if it does not contain a k-star:  so, if we look at any subset of k + 1

vertices U ⊆ V in G, the subgraph of G on the vertices in U is not a k-star.          [10]

(a) For each positive integer k ≥ 3, give an example of a graph G k  = (Vk, Ek) that is k-star free but has a vertex with degree greater thank.

(b)  Consider the following weighted version of the Independent Set problem. The input is a graph G = (V, E) with a non-negative integer vertex weight w(u) ≥ 0 for each u ∈ V. The goal is to find an independent set U ⊆ V in G such that w(U) :=Σu∈U w(u) is maximized. For any k ≥ 3, give a polynomial-time k-approximation algorithm for the Weighted Inde-

pendent Set problem on k-star free graphs. (Hint: Use the obvious greedy algorithm!)

2. Consider the Max SAT problem. As input, you receive a CNF formula F = C1  ∧ C2  ∧ · · · ∧ Cm on n variables.  The goal is to find a boolean assignment x  ∈ {0, 1}n  which satisfies as many clauses as possible.

Prove that the following is a 2-approximation algorithm for the Max SAT problem.  Given F, output the all-1s assignment or the all-0s assignment, whichever satisfies more clauses.        [10]

3. Updated on April 1st. Consider the following variation of the Weighted Vertex Cover problem. As input you receive a graph G = (V, E) with vertex weights w(u) ≥ 0 for all u ∈ V. The goal is to find a subset of vertices U ⊆ V such that [10]

is minimized. In other words, the set U does not have to be a vertex cover: it can leave some edges uncovered, but must pay for each uncovered edge.

(a)  Create an integer program that solves the above variant of the Weighted Vertex Cover problem exactly. Your integer program should have a variable xu  ∈ {0, 1} for every vertex u ∈ U and a variable ye  ∈ {0, 1} for every edge e ∈ E.

(b) Now, find a polynomial-time 3-approximation algorithm for this problem by rounding a solution of the linear programming relaxation of your integer program from part (a).