CSCI 570 Summer2015 HW8 1 State True False If A p B and B N P then A N P 2 State True False If A p B and A N P complete then B N P complete 3 State True False Assume you have a polynomial time algorithm that given a 3 SAT instance decides in polynomial time if it has a satisfying assignment Then you can build a polynomial time algorithm that finds a satisfying assignment if it exists to a given 3 SAT instance 4 State True False If someone proves P N P then it would imply that every decision problem can be solved in polynomial time 5 State True False Assume P 6 N P Let A and B be decision problems If A N P Complete and A P B then B P 6 State True False Assume P 6 N P Let A and B be decision problems If A P and B N P Complete then A P B 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 are restricted to graphs with only even degree vertices 9 Given an undirected graph G V E the Half Clique problem is to decide if there is a subset A V of vertices satisfying the following two conditions i A V2 ii For every pair of vertices u v A if u 6 v then u v E Show that Half Clique is in N P Complete You are allowed to use the fact that Independent Set is in N P Complete 10 Given an undirected graph G and a positive integer k consider the decision problem which asks if a simple path no repeating vertices of length at least k exists 1 Is this decision problem in NP Assuming P 6 NP is it in P 11 Given an undirected graph with positive edge weights the BIG HAMCYCLE problem is to decide if it contains a Hamiltonian cycle C such that the sum of weights of edges in C is at least half of the total sum of weights of edges in the graph Show that BIG HAM CYCLE is NPComplete You are allowed to use the fact that deciding if an undirected graph 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 denotes the number of pebbles stones placed on v We will now play a game where the following move is the only move allowed You can pick a vertex u that contains at least two pebbles and remove two pebbles from u and add one pebble to one your choice of the neighboring vertices of u The objective of the game is to perform a sequence of moves such that we are left with exactly one pebble in the whole graph Show that the problem of deciding if we can reach the objective is NP complete 13 Assume that you are given a polynomial time algorithm that decides if a directed graph contains a Hamiltonian cycle Describe a polynomial time algorithm that given a directed graph that contains a Hamiltonian cycle lists a sequence of vertices in order that form a Hamiltonian cycle 2