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)