# Self-reducibility of Clique

I am trying to understand the following algorithm for Self reducibility of Clique.

Here we have a "MBClique" black box algorithm, which return yes/no for parameters where G is a graph and K is a natural number. It answers the question: "Does G has a clique of K size?" - Our aim is then to use this Decision algorithm to search what the actual Clique graph is.

Given this Graph below, we can see it has a clique of size 3.

The search algorithm is as follows (it was extracted from the CSE 200: Computability and Complexity @ UCSD lecture notes, page 4):

Ok, so now given an algorithm MBClique that returns yes/no we are trying to search the actual k-clique. Suppose the graph of the image above is sent as parameter and k=3.

1. In the first if it passes through.
2. In the immediate after For loop all edges that don't affect the size of the clique are removed.
3. Now my question: what is the Repeat...Until part of the algorithm for? In my understanding after the For loop I already have the respective Graph that I want as an answer.

Thanks.

• I think it's not necessary, maybe to ease the proof. Clearly $G_n$ contains a clique of size $k$, if it is not a $k-\text{clique}$ then there is some excess vertex $v_i$. Since $G_n$ is a subgraph of $G_i$, $G_i\setminus v_i$ contains a $k$ size clique, so it would have been deleted. Commented Sep 8, 2015 at 12:38
• Thanks, I am not sure I understand. My question is then why this second loop (repeat...until) would it pick "arbitrarily" vertices from G and remove it until |V|=k? By removing arbitrary vertices wouldn't it risk removing a vertex from the actual clique? Commented Sep 8, 2015 at 12:52
• It wouldn't hurt. If $G$ is already a $k-\text{clique}$ then the loop will stop immediately (since you already have $k$ vertices). Commented Sep 8, 2015 at 13:01
• We prefer that you avoid using images for algorithms / pseudocode / mathematics. This makes your question impossible to search and inaccessible to the visually impaired, which is unfortunate. I encourage you to transcribe text and mathematics (note that you can use LaTeX).
– D.W.
Commented Sep 8, 2015 at 16:32

If the graph $G$ has no $K$-clique, then this procedure correctly halts. So assume the graph $G$ has at least one $K$-clique. The interesting case is where it has multiple $K$-cliques.
Associate each $K$-clique with a vector $(x_1,x_2,\dots,x_K)$ representing the vertices of the clique, in increasing order. Now order these cliques by lexicographic order on the vectors. Let's focus on the $K$-clique whose corresponding vector is lexicographically largest; call this the "golden" $K$-clique. It is possible to prove that For loop removes everything but the "golden" $K$-clique: when the For loop terminates, all that remains is a subgraph containing exactly $K$ vertices, namely, the golden $K$-clique. Therefore, the Repeat loop does nothing.