1
$\begingroup$

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.

Graph with a clique size 3

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

K-clique search algorithm

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.

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – Ariel
    Sep 8 '15 at 12:38
  • $\begingroup$ 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? $\endgroup$
    – testTester
    Sep 8 '15 at 12:52
  • $\begingroup$ It wouldn't hurt. If $G$ is already a $k-\text{clique}$ then the loop will stop immediately (since you already have $k$ vertices). $\endgroup$
    – Ariel
    Sep 8 '15 at 13:01
  • $\begingroup$ 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). $\endgroup$
    – D.W.
    Sep 8 '15 at 16:32
3
$\begingroup$

The Repeat loop is not strictly necessary. The algorithm would still be correct without it. In fact, the Repeat loop actually has no effect, though proving this takes a little bit of work.

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.

In other words, you can remove the Repeat loop, and this procedure will always produce the same output. (In particular, you were worired that the Repeat loop might remove a vertex from an actual clique -- but the above reasoning shows that this can never happen.)

So, the Repeat loop is unnecessary. Why is it there? Maybe to make the proof of correctness for this algorithm a bit easier. But if you find the algorithm easier to understand if you omit the Repeat loop, go ahead and pretend it's been removed -- that will work, too.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.