Description
1. Clique and Dense Subgraph Problem
a) Given a graph G, and a number k ≥ 0, does G have a clique of size k, where a clique is a subset of vertices
such that every two distinct vertices in the subset are adjacent. Show that this problem is NP-complete.
b) Dense Subgraph Problem: Given graph G = (V, E), numbers k, m ≥ 0. Does there exist a subgraph G’ =
(V’, E’) of G, such that V’ has at most k vertices and E’ has at least m edges. Prove that the Dense Subgraph
Problem is NP-Complete.
2. Connected Independent Set Problem
Given a connected graph G = (V, E), and a number k, does there exist an Independent Set of size k in G
such that the subgraph after removing these vertices is still connected? Prove that the Connected Independent Set Problem is NP-complete.
3. Set Packing Problem
There are n courses at USC, each of them scheduled in multiple disjoint time intervals. For example, a
course may require the time from 9am to 11am and 2pm to 3pm and 4pm to 5pm (you can assume that
there is a fixed set of possible intervals). You want to know, given n courses with their respective intervals,
and a number K, whether it’s possible to take at least K courses with no two overlapping (two courses
overlap if they have at least one common time slot). Prove that the problem is NP-complete.
4. 3-SAT(15/16) Problem
Consider the partial satisfiability problem, denoted as 3SAT(α) defined with a fixed parameter α where
0 ≤ α ≤ 1. As input, we are given a collection of k clauses, each of which contains exactly three literals
(i.e. the same input as the 3-SAT problem from lecture).
The goal is 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 for
α = 1, we require all k clauses to be true, thus 3-Sat(1) is exactly the regular 3-SAT problem. Prove that
3-Sat(15/16)is NP-complete First show that the 3SAT(15/16) problem is in NP:
5. Vertex Cover on Even Degree Graph Problem
Consider the vertex cover problem that restricts the input graphs to be those where all vertices have even
degree.
Call this problem VC-EDG. Show that VC-EDG is NP-complete.
First show that the VC-EDG problem is in NP:
6. Transitivity of Polynomial Time Reduction
Let S be an NP-complete problem, and Q and R be two problems whose classification is unknown (i.e. we
don’t know whether they are in NP, or NP-hard, etc.).
We do know that Q is polynomial time reducible to
S and S is polynomial time reducible to R. Mark the following statements True or False based only on the
given information, and explain why.
