CSCI 570-Summer2015- HW81. State True/False. If A ≤pB and B ∈ NP , then A ∈ NP .2. State True/False. If A ≤pB and A ∈ NP -complete, then B ∈ N P -complete.3. State True/False. Assume you have a polynomial time algorithm thatgiven a 3-SAT instance, decides in polynomial time if it has a satisfyingassignment. Then you can build a polynomial time algorithm that finds asatisfying assignment(if it exists) to a given 3-SAT instance.4. State True/False. If someone proves P = NP , then it would imply thatevery decision problem can be solved in polynomial time.5. State True/False. Assume P 6= NP . Let A and B be decision problems.If A ∈ NP -Complete and A ≤PB, then B /∈ P .6. State True/False. Assume P 6= NP . Let A and B be decision problems.If A ∈ P and B ∈ NP -Complete, then A ≤PB.7. Given an n bit positive integer, the problem is to decide if it is composite.Here the problem size is n. Is this decision problem in NP ?8. Show that vertex cover remains N P -Complete even if the instances arerestricted to graphs with only even degree vertices.9. Given an undirected graph G = (V, E), the Half-Clique problem is to de-cide if there is a subset A ⊆ V of vertices satisfying the following twoconditions:(i) |A| ≥|V |2(ii) For every pair of vertices u, v ∈ A, if u 6= v, then (u, v) ∈ E.Show that Half-Clique is in NP -Complete. You are allowed to use thefact that Independent-Set is in NP -Complete.10. Given an undirected graph G and a positive integer k, consider the deci-sion problem which asks if a simple path (no repeating vertices) of lengthat least k exists.1Is this decision problem in NP ? Assuming P 6= NP, is it in P ?11. Given an undirected graph with positive edge weights, the BIG-HAM-CYCLE problem is to decide if it contains a Hamiltonian cycle C suchthat the sum of weights of edges in C is at least half of the total sumof weights of edges in the graph. Show that BIG-HAM-CYCLE is NP-Complete. You are allowed to use the fact that deciding if an undirectedgraph has a Hamiltonian cycle is NP-complete.12. You are given an undirected graph G = (V, E) and for each vertex v ∈ V ,you are given a number p(v) (which is either 0 or 1 or 2) that denotesthe number of pebbles (stones) placed on v. We will now play a gamewhere the following move is the only move allowed. You can pick a vertexu that contains at least two pebbles, and remove two pebbles from u andadd one pebble to one (your choice) of the neighboring vertices of u. Theobjective of the game is to perform a sequence of moves such that we areleft with exactly one pebble in the whole graph. Show that the problemof deciding if we can reach the objective is NP-complete.13. Assume that you are given a polynomial time algorithm that decides if adirected graph contains a Hamiltonian cycle. Describe a polynomial timealgorithm that given a directed graph that contains a Hamiltonian cycle,lists a sequence of vertices (in order) that form a Hamiltonian