Problems

Recall that a k$-$clique in a simple graph $G=(V,E)$ is a subset CsubeV of $k$ vertices for which,

if $u,$vinC, then $(u,v)inE.$ In other words, $C$ is a k$-$clique iff $|C|=k$ and each pair of vertices

in $C$ are joined by an edge of the graph $G.$ For example, the graph $G=(V,E)$ shown below

has several $3-$cliques, namely $\{1,4,5\},\{1,3,5\},\{1,3,6\},\{2,3,6\},$ and $\{3,5,6\}.$ Moreover, an

instance of the Max Clique optimization problem is a simple graph $G=(V,E)$ and the problem

is to find a clique of largest size in $G.$ Also, an instance of the Clique decision problem is a

simple graph $G=(V,E)$ and a nonnegative integer $k,$ and the problem is to decide if $G$ has a

$k-$clique.

$($a$)$ Describe an algorithm that establishes Max Clique ${?}_T^p$ Clique. In other words, the

algorithm should be able to compute a maximum$-$sized clique for $G$ by making queries to

a Clique$-$oracle about whether or not a graph has a clique of some size $k.$ Moreover, the

algorithm should require at most $O(m+n)$ steps, where $m=|E|$ and $n=|V|.$ Hint: first

use the oracle to determine the size of the largest clique, and then use it to determine the

vertices of the clique. The latter part should involve querying the oracle about different

subgraphs of $G.(20$ pts$)$

$($b$)$ After describing the algorithm, provide high$-$level pseudocode that more carefully describes

the algorithm. $(10$ pts