## Description

Q1) (20pts) Given a graph G = (V, E) and two integers k, m, a clique is a subset of vertices

such that every two distinct vertices in the subset are adjacent.

a) The Clique problem asks: Given a graph G, and a number k ≥ 0, does G have a clique

of size k. Show that this problem is NP-complete. Hint: Reduce from Independent

Set.

b) The Dense Subgraph Problem is to determine if given graph G, and 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.

Q2) 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. (20 points)

Hint: Use a reduction from the Independent Set problem to show NP-hardness

Q3: Consider the partial satisfiability problem, denoted as 3-Sat(α) 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. (20 points)

Hint: If x, y, and z are variables, note that 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)

Think about how many of these are true for a given assignment of x, y, and z.

4) 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.

(15pts)