$30
CSCI 570 Homework 10 1 Graded Problems 1. True/False Questions (9pt) State True or False for the following sentences and give a brief explanation. (a) If someone proves P=NP, then it would imply that every decision problem can be solved in polynomial time. (b) Assume A is a decision problem, If A ≤p B and B ∈ NP, then A ∈ NP. (c) Assume P ̸∈ NP. Let A and B be decision problems. If A ∈ NP C and A ≤p B, then B ∈ P. 2. Show that vertex cover remains NP-Complete even if the instances are restricted to graphs with only even degree vertices. (15pts) 3. Consider the partial satisfiability problem, denoted as 3-Sat(α). We are given a collection of k clauses, each of which contains exactly three literals, and we are asked to determine whether there is an assignment of true/false values to the literals such that at least αk clauses will be true. Note that 3-Sat(1) is exactly the 3-SAT problem from lecture. Prove that 3-Sat(15/16)is NP-complete. (20 points) Hint: If x, y, and z are literals, there are eight possible clauses containing them: (x ∨ y ∨ z),(!x ∨ y ∨ z),(x ∨ !y ∨ z),(x ∨ y ∨ !z),(!x ∨ !y ∨ z),(!x ∨ y ∨ !z),(x ∨ !y ∨ !z),(!x ∨ !y ∨ !z) 4. Given a graph G = (V, E) and two integers k, m, the Dense Subgraph Problem is to find a subset V ′ of V , whose size is at most k and are connected by at least m edges. Prove that the Dense Subgraph Problem is NP-Complete.(20 pts) 2 Ungraded Problems 1. There are N cities, and there are some undirected roads connecting them, so they form an undirected graph G(V, E). You want to know, given K and M, if there exists a subset of cities of size K, and the total number of roads between these cities is larger or equal to M. Prove that the problem is NP-Complete. 2. Suppose we have a variation on the 3-SAT problem called Min-3-SAT, where the literals are never negated. Of course, in this case it it possible to satisfy all clauses by simply setting all literals to true. But, we are additionally given a number k, and are asked to determine whether we can satisfy all clauses while setting at most k literals to be true. Prove that Min-3-SAT is NP-Complete. 1 of 1 Professor: Dr. Shahriar Shamsian