## 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.