MAX$-$CLIQUE. Given a directed graph G$,$ find the size of the largest subset S of the vertices in G$,$ such that all the vertices in S are adjacent $($S is called a max$-$clique$).$

Examples.

G The MAX$-$CLIQUE G The MAX$-$CLIQUE

is of size $4$ is of size $3$

A$.$ Draw a $($large and clear$)$ tree showing how a brute force algorithm enumerates all the possible solutions for the graph given on the right.

Make sure to clearly indicate:

What each edge in the tree represents.

Feasible candidate solutions.

Infeasible candidate solutions.

B$.$ What is the running time of the brute force algorithm? Express your answer using V $($the number of vertices in G$)$ and use Big$-$Theta notation.

C$.$ Suggest a backtracking strategy for improving the running time of the brute force solution.