W2. [6 marks] In this question, we will consider two possible backtracking algorithms for CLUSTER PARAMETERIZED BY CLUSTER SIZE, defined as follows:
Input: A graph $G$ and a positive integer $k$
Output: Yes or no, answering “Is there a cluster in $G$ of size $k$?
Parameter: $k$
For each of the algorithms described below, answer the following two questions:
• Is the worst-case running time of the algorithm in $f(k) \cdot n^{O(1)}$?
• Is the proposed algorithm guaranteed to produce the correct answer?
(a) [3 marks] Form a search tree in which the root corresponds to the empty set. At each node, form a child for each node not already in the set that is a neighbour of all nodes in the set (vacuously true for the empty set). Stop after $k+1$ levels, producing true if a node is formed and false otherwise.
(b) [3 marks] Order the vertices. Form a search tree in which the root corresponds to the empty set. At each node, for the next vertex in order, create one set that contains the vertex (if it and the current contents of the set form a cluster) and one that does not contain the vertex. Stop after $k+1$ levels, producing true if a node is formed and false otherwise.
