CSCI570 Homework 10 Solution

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.
Hint: Use a reduction from the Independent Set problem to show NP-hardness
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)
UNGRADEDPROBLEMS
Q5: 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.
(i) Q is NP-complete (4pts)
(ii) Q is NP-hard (4pts)
(iii) R is NP-complete (4pts)
(iv) R is NP-hard (4pts)