Given an undirected graph G=(V, E) where V={x1, x2,···xn}. A clique is a subgraph G0 of G, where G0=(V0,E0) with V0⊆V, E0⊆E, and for any xi, xj∈V0 with i?=j, (xi,xj)∈ E0. A clique is called m-clique if the cardinality (number of vertices) of V0 is m.
Assume that n » 9 (n is much larger than 9) and it takes O(1) time to check whether (xi,xj) ∈ E.
1. Design an O(n9) algorithm to find a 9-clique in G, if such clique exists; answer "no such a clique" if it does not exist. Please describe your algorithm and sketch its correctness. Pseudocode is NOT required.
2. Prove that a set of vertices is a 9-clique if and only if it can be partitioned into 3 disjoint 3-cliques such that the union of any two of them forms a 6-clique.
3. Show how to find a 9-clique in G in time O(nδ) for some δ < 9, if such a clique exists. Please describe your algorithm and sketch its correctness. Pseudocode is NOT required.(Hint: consider the fast matrix multiplication problem.)