Homework #6 Solution



  1. Consider the problem Find-IS 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 Independent-Set 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 polynomial-time reduction from Find-IS to Independent-Set. [.75 points]

  1. Give a polynomial-time Karp reduction from 3SAT to Vertex-Cover. For full-credit 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 Independent-Set. [.75 points]

  1. Consider the problem LPS de ned as follows: \Given a matrix A 2 Rn n, a vector b 2 Rn and an integer k > 0, does there exist a vector x 2 Rn with at most k non-zero entries such that A x b”. Here A x denotes the usual matrix-vector product and for two vectors u; v, we say u v if for every i, ui vi. Give a polynomial-time reduction from 3SAT to LPS. [.75 points]

(Hint: Use the reductions done in class along-with transitivity of P to rst pick the \right” starting point and then design a reduction from this starting point.)

  1. Show that the following problems are in NP.

  1. 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 GraphI-somorphism is in NP.

  1. 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 3-coloring of a G is a mapping : V ! f1; 2; 3g such that for any adjacent vertices u; v, (u) 6= (v). Consider the problem Find-3Coloring de ned as follows: \Given a graph G, nd a valid 3-coloring of G if one exists.” and the 3Coloring decision problem from class: \Given a graph G, is there a valid 3-coloring of G”. Give a polynomial-time reduction from Find-3Coloring to 3Coloring. You don’t have to prove correctness or analyze time-complexity.

[Hint: Note that if jV j 4, then two vertices must get the same color in any proper 3-coloring. Use the black-box 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 multi-variate polynomials over variables x1; : : : ; xn

and how they are speci ed. To review some terminology, we say a monomial is a product of a real-number co-e cient c and each variable xi raised to some non-negative integer power ai: we can write this as cxa11 xa22 xann . A polynomial is then a sum of a nite set of monomials. (For example, 2x21x2x43 + x1x3 6x22x23 is a polynomial.)

We say a polynomial P is of degree at most d, if for any monomial cxa11 xa22 xann appearing in P , a1 + a2 + an d. (For example, the degree of the previous polynomial is 7). One can represent a n-variable polynomial of degree d by at most (n + 1)d numbers (by d-dimensional 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 Poly-Root 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 Rn such that P (x) = 0.” Show that 3SAT is polynomially easier than Poly-Root. 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 (a1; : : : ; am), Pi a2i = 0 if and only if ai = 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].