0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$ – Iam Spano Mar 23 at 19:56
  • $\begingroup$ 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). $\endgroup$ – Steven Mar 23 at 19:59
  • $\begingroup$ 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$. $\endgroup$ – Steven Mar 23 at 20:06
  • $\begingroup$ Got it, thanks a lot! $\endgroup$ – Iam Spano Mar 23 at 20:27

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.