Final assignment

You may consult relevant references, but should write your answers on your own (no copy-paste from other sources). It is advisable to include drawings in your answers, wherever applicable. (No need to spend much time on producing electronic drawings- they can be drawn by hand.) Please hand in your exam on or before July 22, 2011. 1. The sparsity of a cut induced by a set S of vertices in an unweighted graph G = (V,E) is the ratio between the number of edges jE(S, V nS)j crossing the cut and the product jSj jV nSj of sizes. Show that for some ϵ> 0 it is R3SAT-hard (in the sense of [3]) to approximate sparsest cut within a ratio better than 1 + ϵ. In designing the reduction and proving its correctness, you may consult [1] (or versions of that paper available of the home pages of its authors). 2. For a d-regular unweighted graph G = (V,E), let 1 = λ1 λ2 λn be its normalized eigenvalues, i.e. the eigenvalues of the matrix whose ij-th entry is 1/d if there is an edge from i to j and zero otherwise. Prove that for some constant c> 0 and every ϵ, β> 0 there is a polynomial-time algorithm that when given as input a d-regular graph G over n vertices with at least nc normalized eigenvalues above 1 ϵ it outputs a set S satisfyin