Answered You can hire a professional tutor to get the answer.
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 V0V, E0E, and for any xi, xjV0 with...
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.)
