Homework #4
COSC 5110
Analysis of Algorithms
1. Exercise 2.27.
2. Exercise 5.3.
3. Exercise 6.17.
4. Recall the CLIQUE decision problem: given a graph G and a number k, does G have a clique
of size k?
(a) Show that if CLIQUE is in P, then there is a polynomial-time algorithm that takes a
graph G as input and outputs the size of a largest clique in G.
(b) Show that if CLIQUE is in P, then there is a polynomial-time algorithm that takes a
graph G as input and outputs a largest clique in G.
1
