I have a question that is not clear to me, and I have not been able to answer it from a test I had.

This is the question:

Let's look at the problem $Oclique$ , In it we get a graph $G = (V,E)$ , And an odd natural number $k \in N$ ( You can mark: $k = 2d + 1$ for $d \in N $) And ask: "Is there a $U \subseteq V$ clique so that $| U | = k$?"

The language is:

$OClique = ${ $\left \langle G,k \right \rangle$ | There a $U \subseteq V$ clique so that $| U | = k$ and also $k = 2d + 1$ for $d \in N $ and for every $u_1,u_2 \in U$ there is an $(u_1,u_2 )\in E$.}

Determine which of the claims is correct:

  1. The language is in $\mathsf{NP}$ but not in $\mathsf{NPH}$ and not in $\mathsf{NPC}$.

  2. The language is in $\mathsf{P}$ because an algorithm can be constructed running at time O (| V | * | E |), by reduction to the IS problem.

  3. The language is in $\mathsf{NPC}$ And this is why $Clique \leq _p OClique$ conversion can be found.

  4. The language is in $\mathsf{NPH}$ but not in $\mathsf{NP}$ and not in $\mathsf{NPC}$.

  5. None of the above claims are true.

I think the answer is 3, but I'm not sure how to do the reduction.

  1. Wrong, I think it is possible to make a reduction from the Clique problem
  2. Does not make sense in any way. It does not belong to P. Reduction from IS which is NPC, will also lead to OClique in NPC.
  3. I think this is true, it is possible to convert any instance from the Clique problem to the OClique problem and vice versa. Each graph in Clique, you can multiply by 2 the amount of vertices, and connect the vertices to all the other vertices, then add one more vertex to all the other vertices. I think this is a complete, correct, and polynomial time reduction, but I'm not sure if I explained it properly.
  4. It does not make sense, if the language is in NPH then it is also in NP.
  5. maybe 3 is true.

I think the answer is 3, I'm not sure then explain it properly.


1 Answer 1


1 is wrong. The problem is NP-Complete by an easy reduction $f$ from the clique problem. Let $\langle G,k \rangle$ with $G=(V,E)$ be an instance of (the decision version of) clique. If $k$ is odd then the reduction is the identity function, i.e., $f(\langle G,k \rangle)=\langle G,k \rangle$. Otherwise create a new graph $G=(V', E')$ with $V' = V \cup \{v\}$ and $E'= E \cup (\{v\} \times V)$ and let $f(\langle G,k \rangle)=\langle G',k+1 \rangle$. This also shows that 3 is true (a certificate for $OClique$ is the list of vertices in a clique of size at least $k$).

We currently don't know whether 2 is true or false. It if were true it would prove $P=NP$.

Regarding 4. The language is in NP so this is false. Notice however that, in general, a NP-hard problem does not necessarily need to be in NP.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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