• 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)
• 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
