Find a Cook Reduction from $R_{Clique}$ to its determinist problem

The question is to find Find a Cook Reduction from $$R_{k-Clique}$$ to its determinist problem.

Basically:

k-Clique: a group of $$k$$ nodes in the graph such there is an edge between every two nodes.

Suppose you are allowed to use an algorithm (B) that in $$O(1)$$, given as input a graph $$G$$ and a number $$k$$, returns whether the graph includes a $$k-Clique$$ or not.

Use B to define an algorithm (A), that in polynomial time, given as input a graph $$G$$ and a number $$k$$, returns a $$k-Clique$$ if it exists, and a symbol if it doesn't.

My idea:

My idea was to define something as follow:

1. While the size of the graph is greater than k
2. Remove from the graph the node with the lowest deg
1. check the new G with B, if yes, return it
2. Else, continue

Something like that. I wasn't able to disprove it at least. But is it correct? How would I prove it?

Your algorithm doesn't return a $$k$$-clique. Simply consider a connected graph $$G$$ that is a proper supergraph of a $$k$$-clique, and an isolated vertex $$x$$. Your algorithm with input $$G+x$$ returns $$G$$.

You can solve your problem as follows:

• While $$\exists$$ a vertex $$v$$ of $$G$$ such that $$B(G-v)$$ returns true:
• Delete $$v$$ from $$G$$
• Return $$G$$.

Let $$G^* = (V^*, E^*)$$ be the graph returned by the algorithm. Since the algorithm preserves the invariant "G contains a $$k$$-clique", $$G^*$$ must also contain a $$k$$-clique. This means that we only need to prove that $$G^*$$ is not a supergraph of a $$k$$-clique.

Suppose towards a contradiction that there exists a proper subset $$C$$ of $$V^*$$ such that $$|C|=k$$ and the subgraph of $$G^*$$ induced by $$C$$ is a $$k$$-clique. Then, for any vertex in $$v \in V^* \setminus C \neq \emptyset$$, $$G-v$$ also contains a $$k$$-clique. This shows that the algorithm cannot return $$G^*$$ and yields the sought contradiction.

• Thanks for the help, I understand your algorithm and proof, but I have two questions: 1. Notice how my algorithm runs "While the size of the graph is greater than k", so in your initial example I don't think I would return $G$: I would continue to run. 2. What is the time complexity of your algorithm? Is it polynomial? We repeat it $k$ times, each time I have to remove an edge and do the check, for $G-i$ nodes Mar 23 '21 at 19:56
• Your algorithm says: "1 While the size of the graph is greater than $k$. In my case it is, so we proceed to step 1.2. Step 1.2 is "Remove from the graph the node with the lowest degree", so we remove $x$ from the input graph $G+x$ and we are left with $G$. The next instruction is 1.2.1: "Check the new G with B, if yes, return it". The new graph is $G$ and contains a $k$-clique, so $B$ returns "yes", and your algorithm returns $G$. However $G$ is not a $k$-clique (it just contains it). Mar 23 '21 at 19:59
• My algorithm does run in polynomial time. A trivial implementation evaluates the condition of the while loop at most $n-k+1$ times. Each evaluation runs $B$ $O(n)$ times. A better analysis uses the fact that if a vertex cannot be removed in one iteration, then it belongs to all $k$-cliques of $G$ and hence it won't be removed in any following iterations. Therefore $n$ iterations suffice. To summarize, you can just consider one vertex $v \in V$ at a time and do the following: if $B(G-v)$ returns true then delete $v$ from $G$. Once all vertices $v$ have been considered, return $G$. Mar 23 '21 at 20:06
• Got it, thanks a lot! Mar 23 '21 at 20:27