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.
- In the first if it passes through.
- In the immediate after For loop all edges that don't affect the size of the clique are removed.
- 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.