$30.00
Description

Consider the problem FindIS de ned as follows: \Given a graph G and a number k as input, nd an independent set of size k in G if one exists.” Recall the IndependentSet decision problem from class: \Given a graph G and a number k, does G contain an independent set of size at least k?”. Give a polynomialtime reduction from FindIS to IndependentSet. [.75 points]

Give a polynomialtime Karp reduction from 3SAT to VertexCover. For fullcredit for this problem, you should not use transitivity but have to show the three steps as we did in class for the reduction from 3SAT to IndependentSet. [.75 points]

Consider the problem LPS de ned as follows: \Given a matrix A 2 R^{n n}, a vector b 2 R^{n} and an integer k > 0, does there exist a vector x 2 R^{n} with at most k nonzero entries such that A x b”. Here A x denotes the usual matrixvector product and for two vectors u; v, we say u v if for every i, u_{i} v_{i}. Give a polynomialtime reduction from 3SAT to LPS. [.75 points]
(Hint: Use the reductions done in class alongwith transitivity of _{P} to rst pick the \right” starting point and then design a reduction from this starting point.)

Show that the following problems are in NP.

Given two graphs G = (V; E) and H = (W; F ), we say G; H are isomorphic if there
exists a bijection : V ! W such that for any two u; v 2 V , fu; vg 2 E if and only if f (u); (v)g 2 F (i.e., two vertices u; v 2 V are adjacent if and only if f (u); (v)g are adjacent).
Let GraphIsomorphism = f(G; H) : G,H are isomorphic graphsg. Show that GraphIsomorphism is in NP.

Given a graph G = (V; E), a subset of vertices I is a dominating set if every vertex in
the graph is either in I or adjacent to a vertex in I. Let DominatingSet = f(G; k) :
G has a dominating set of size kg. Show that DominatingSet is in NP.
Additional Problems. DO NOT turn in answers for the following problems – they are meant for your curiosity and understanding.
1* Given a graph G = (V; E), a valid 3coloring of a G is a mapping : V ! f1; 2; 3g such that for any adjacent vertices u; v, (u) 6= (v). Consider the problem Find3Coloring de ned as follows: \Given a graph G, nd a valid 3coloring of G if one exists.” and the 3Coloring decision problem from class: \Given a graph G, is there a valid 3coloring of G”. Give a polynomialtime reduction from Find3Coloring to 3Coloring. You don’t have to prove correctness or analyze timecomplexity.
[Hint: Note that if jV j 4, then two vertices must get the same color in any proper 3coloring. Use the blackbox access to 3Coloring to nd two vertices that can get the same color and use this to decrease the size of the graph you are working with and repeat.]

For this problem we need the notion of multivariate polynomials over variables x_{1}; : : : ; x_{n}
and how they are speci ed. To review some terminology, we say a monomial is a product of a realnumber coe cient c and each variable x_{i} raised to some nonnegative integer power a_{i}: we can write this as cx^{a}_{1}^{1} x^{a}_{2}^{2} x^{a}_{n}n . A polynomial is then a sum of a nite set of monomials. (For example, 2x^{2}_{1}x_{2}x^{4}_{3} + x_{1}x_{3} 6x^{2}_{2}x^{2}_{3} is a polynomial.)
We say a polynomial P is of degree at most d, if for any monomial cx^{a}_{1}^{1} x^{a}_{2}^{2} x^{a}_{n}n appearing in P , a_{1} + a_{2} + a_{n} d. (For example, the degree of the previous polynomial is 7). One can represent a nvariable polynomial of degree d by at most (n + 1)^{d} numbers (by ddimensional arrays for instance – but let us ignore the actual details of the representation as this is not important and any representation will work for us).
Consider the problem PolyRoot de ned as follows: \Given a polynomial with integer coe cients of degree at most 6 as input, decide if there exists a x 2 R^{n} such that P (x) = 0.” Show that 3SAT is polynomially easier than PolyRoot. You don’t have to write down the coe cients of the polynomials explicitly in your reduction – you can leave them as summations if it is more convenient for you (one reason why we didn’t specify the exact representation). Hint: Try to de ne a polynomial equation for each clause in your 3SAT instance along with
some other equations for variables and combine them into one big polynomial by using the fact that for any set of numbers (a_{1}; : : : ; a_{m}), ^{P}_{i} a^{2}_{i} = 0 if and only if a_{i} = 0 for all i 2 [m].
3 Chapter 8, Problems 1,3, 6, 26, 27, 30, 31, 41 from [KT]
4 Problems 8.3, 8.4, 8.6, 8.8, 8.14, 8.23 from Chapter 8 of [DPV].
2