Directions: Do all problems. 

Homework 6 Due Monday, May 23 2022 The Graph Coloring Problem This homework set is a case study of the graph coloring problem. Over the course of the next few problems you will (1) show that this problem is NPhard via a reduction from 3SAT; (2) devise a basic approximation algorithm for this problem; (3) devise a better approximation algorithm using semi-definite programming. Good luck and have fun :-) The Coloring Problem and NPHardness Given a graph G = (V,E), a kcoloring of G is an assignment of one out of k colors to each vertex such that no edge in the graph is monochromatic. Formally, a kcoloring is a function : V {1,...,k} such that for all e = (v,w) E, (v) = (w). We say that G is kcolorable if it admits a kcoloring. The algorithmic problem is kCOL: given G = (V, E), find a kcoloring for G if one exists. The first problem asks you to show that 3COL is NPhard by analyzing a reduction from 3SAT. Consider the following transformation algorithm which takes a 3SAT instance = 1 m, where each = xi xj xk is the OR of three literals, and outputs the following graph G: Vertices: There are three types of vertices. There is one vertex for every literal (so two for every variable xi, vertex vxi corresponds to the literal xi, vxi corresponds to the literal xi). These are called the literal vertices. For each i, vxi and vxi are connected by an edge. There are six vertices for each clause, arranged with edges into two triangles like in the picture below. We refer to these as the clause gadgets; for each = 1, . . . , m there is a clause gadget corresponding to . There are three special vertices, vtrue, vfalse, and vground which are arranged in a triangle and are all connected to one another. Edges: In addition to the edges described above there are also the following two types of edges: Every literal vertex is connected to vground. 1 1 34 2 Every gadget vertex number 6 is connected to vfalse and vground; additionally, for every = 1, . . . , m, vertices 1, 2, and 5 in the gadget corresponding to are connected (in any order) to the three literals of . Problem 1. Suppose we have an algorithm A which solves 3COL, and consider the three-step algorithm for solving 3SAT: 1) given , run the above transformation obtaining the graph G; 2) call A(G) to obtain a 3coloring for G if one exists; 3) translate the 3coloring (if found) back into an assignment to the 3SAT variables. Do the following: (a) Show that if is satisfiable then G is 3colorable. (b) Describe the transformation procedure of step 3. Specifically, describe how a 3coloring for G is converted back into an assignment to the variables of . (c) Show that when a 3coloring for G is converted back to an assignment for the variables of , this assignment satisfies all clauses of . (d) Combine (a), (b) and (c) to conclude that an algorithm which efficiently solves 3COL can be used to construct an efficient algorithm which solves 3SAT. This proves that 3COL is NPhard. The Relaxed Coloring Problem GraphColk,r We showed above that it is NPhard to find a 3coloring in a 3colorable graph. This motivates the following question: what is the smallest r > k such that we can efficiently find a rcoloring in a kcolorable graph? The corresponding algorithmic problem is GraphColk,r; i.e. GraphColk,r asks us, given a kcolorable graph G, to find an rcoloring for G. We showed above that GraphColk,r is NPhard when k = r = 3. On the other hand, when r = n (where n = |V |), GraphColk,r can be solved efficiently (and trivially) for all k (even k = 3) by simply coloring every vertex with a different color. So the problem GraphCol3,r gets easier as r increases; it starts very hard when r = 3, and eventually becomes easy when r = n. The main question we will focus on for the remainder of this problem set is: can we design an algorithm for GraphCol3,r for 3 < r < n? For simplicity when k = 3, we supress the k, writing GraphColr instead of GraphCol3,r. We begin by considering two cases in which GraphColk,r can be solved efficiently. 2 6 5 Problem 2. Describe an algorithm which solves GraphCol2,2 (i.e., given a 2colorable graph, your algorithm should find a 2coloring). Hint: First, design an algorithm which colors con- nected graphs; then color G one connected component at a time. The problem GraphColk,r refers to the special case of GraphColk,r when the input graph has degree at most . Recall, the degree of a vertex v V is the number of neighbors: |N(v)| = #{w V : (v, w) E}; the degree of a graph G is the maximum degree of any of its vertices. Thus, to insist that the degree of G is at most requires that every vertex has at most neighbors. Formally, the problem GraphColk,r is the following: given a kcolorable graph G with degree at most , output an rcoloring. As before, when k = 3 we write GraphColr instead of GraphCol3,r. Problem 3. Describe an algorithm which solves GraphCol(+1); i.e., your algorithm should, given a graph G of degree at most , output a ( + 1)coloring. Removing the Low Degree Restriction In this section we work through an algorithm which outputs a coloring for a graph G, by making use of subroutines A and B which solve GraphCol2,2 and GraphColr , respectively. We could set r = + 1 and use the algorithm from Problem 3. Later on, we will use SDP to give an efficient algorithm for GraphColr for larger r, and so ultimately we will use this better algorithm. The number of colors in our final coloring will be at most r = r + 3n/. Our algorithm makes use of an operation which shrinks a graph by removing a set of vertices from it. Formally, given a set S V of vertices of a graph G = (V,E), when we remove S from G this means we set G=(V,E)whereV =V\SandE isthesetofedgesinEwhicharenotincidenttoany vertex in S. The algorithm works as follows. Input: A 3colorable graph G = (V, E). 1. While the deg(G) > , do the following: letvV beavertexsuchthat|N(v)|>; color v some color; call AN(v) to color N(v) with 2 colors; remove S = N(v) {v} from G, continue. Output: Output B(G). The key idea behind the algorithm is that since G is 3colorable, every neighborhood must be 2colorable, and so the call to AN(v) works. This is because if G is 3colorable then whatever color v is colored, it must be possible to color N(v) with the remaining two colors (since no vertex in N(v) can be colored the same color as v). Problem 4. Show that the number of colors used by the above algorithm is at most r + 3n/. Deduce the following. (a) if = n and B is the algorithm from Problem 3 (so r = n+1), then the above algorithm solves GraphColO(n). 3 (b) if = nlog6 3, r = O(nlog6 2 log n), and B solves GraphColr (we will describe B over the remainder of the homework), then the above algorithm solves GraphColr where r = O(nlog6 2 log n) + On/nlog6 3 = O(nlog6 2 log n). Semi-Coloring the Graph is Sufficient Definition. Let G = (V,E) be a graph. We say that : V {1,...,k,uncolored} is a ksemi-coloring if the following 2 properties hold: 1. atleasthalfoftheverticesarecolored #vV :(v){1,...,k}|V|/2; 2. no edge with colored endpoints is monochromatic for all e = (v,w) E such that (v), (w) = uncolored, (v) = (w). So, in words, a ksemi-coloring is a kcoloring, except that it is allowed to leave half (or fewer) of the vertices uncolored. Thus, it should be easier to produce a ksemi-coloring than to produce a kcoloring, since the algorithm is able to say I dont know" on up to half of the vertices. Nevertheless, we show in this section that one can solve GraphColrlogn+1 given an algorithm C which solves GraphSemiColr , where GraphSemiColr asks an algorithm to, given a 3colorable graph G of degree at most , output an rsemi-coloring. The algorithm for GraphColrlog n+1 works as follows. Input: A 3colorable graph G = (V, E) of degree at most . 1. If |V | = 1, just output a coloring for G with one color. 2. Otherwise, initialize an empty function ret, and a counter count = 0. While |V | > 1 do the following: call C(G) to recover an rsemi-coloring : V {1, . . . , r, uncolored}; for every v V which is colored by (i.e., so that (v) = uncolored), set ret(v) = count r + (v); remove the set of vertices colored by from G; increment count; continue. Problem 5. Show that the above algorithm outputs an rcoloring of G where r = rlog n+1, assuming that C solves the GraphSemiColr problem. In particular, this means that if C solves log 3 log 2 log 2 GraphSemiColr for = n 6 and r = 3 = n 6 , then the algorithm above solves GraphColr forthesame=nlog63 andr =O(nlog62 logn). An SDP-based Algorithm for Graph Semi-Coloring Finally, we describe our SDP component for semi-coloring a bounded degree graph. Specifically, this algorithm solves the GraphSemiColr problem, where = nlog6 3 and r = 2log3 2. The algorithm works as follows. Input: A 3colorable graph G = (V, E) of degree at most . 4 1. The SDP: Set up and solve the following semidefinite program with vector variables {xv}vV : max 1 s.t. vvvw12 e=(v,w)E |vv| = 1 v V Note we have set our objective to be the constant function 1; this is a common trick when we do not actually need to maximize (or minimize) anything; instead we simply want to find any feasible point which satisfies all the constraints. 2. Rounding: At this stage we have a feasible set of vectors {xv} which satisfy the constraints (assuming the SDP constraints are not infeasible which we will show in part a). Let l=1+log3. Byourchoiceofparameters,wehave3l =3and2l =r. Weassumefor simplicity that l is an integer (even though this is technically not possible; the algorithm can be modified slightly and made to work when this is not the case). Choose l random unit vectors h1,...,hl Rn, and let the (n1)-dimensional planes H1,...,Hl Rn be so that Hi is the plane perpendicular to hi. Note that the l planes chop Rn into 2l = r parts; label these parts P1, . . . , Pr. Define the function : V {1, . . . , r, uncolored} as follows: (i) forallvV,set(v)=iwhereiissuchthatxv Pi; (ii) for all e = (v, w) E, if (v) = (w), change (w) = uncolored. Output: . Problem 6. Show that the algorithm above solves GraphSemiColr by working through the following outline. (a) Suppose G is 3colorable; let : V {1, 2, 3} be a 3coloring and define vector variables {yv}vV as follows: Let p1 = 3, 1,p2 = 3, 1,p3 = (0,1) R2 be the vertices of an equilateral 22 22 triangle in R2. ForvV,letyv =pi wherei=(v). Provethat|yv|=1forallvV andthatyv yw 21 foralle=(v,w)E. Thus{yv} is a feasible solution for the SDP. This, in particular, implies that the SDP is not infeasible and so the algorithm does indeed find vectors {xv} in Step 1 which satisfy all constraints. (b) Let {xv} be the vectors computed in Step 1 by solving the SDP. Prove that for every e = (v,w) E, the angle v,w between xv and xw is at least 2. 3 (c) Deduce that for each of the random (n 1)planes Hi (i = 1, . . . , l), the probability that xv andxw (fore=(v,w)E)arenot separatedbyHi isatmost 31. (d) Deduce that for e = (v,w) E, the probability that the probability that (v) = (w) after Step 3i is at most 1l. 3 5 (e) Deduce that # n 1 Pr {e=(v,w)E:(v)=(w)afterStep3i}2 3. This completes the analysis since it shows that with good probability (i.e., at least 2/3) the number of edges whose endpoints are labeled the same color after Step 3i is at most n/2. In this case, at least n/2 vertices are colored by and so is a semi-coloring. Note, if we want to increase the probability from 2/3 to 1 2(t), we can repeat the rounding step t times using independent randomness; the probability that we never obtain a semi-coloring is at most 1t = 2(t). 3 6