I saw the posted question here about a direct reduction from near-clique to clique.

Clique-or-almost is like near-clique but with the option for a complete clique of size $k$, I mean that perhaps an edge is missing and perhaps not.

I can't figure out how to change the proof in the link to fit to the reduction from Clique-or-almost to Clique.

$$\text{CLIQUE-or-almost} = \{(G,k) \mid \text{ $G$ contains a $k$-clique with possibly one missing edge}\}.$$

  • $\begingroup$ Can you make the post self-contained by adding a definition of near-Clique? A formal definition of the problem you're considering (Clique-or-almost clique) would also help. $\endgroup$ – Steven Nov 7 '19 at 17:48
  • $\begingroup$ I added a formal definition for Clique-or-almost. Near-clique is the same but without the work "possibly". $\endgroup$ – user3343396 Nov 7 '19 at 18:07

If $G=(V, E)$ is the graph of an instance of CLIQUE-or-almost to CLIQUE, then you can create a new graph $G'$ as the disjoint union of $G$ with all the graphs $G + e$ for $e \in \binom{V}{2} \setminus E$.

Then $G$ has a clique or an almost-clique on $k$ vertices if and only if $G'$ has a clique on $k$ vertices.

This shows that CLIQUE-or-almost $\le_p$ CLIQUE. You can also show a polynomial reduction from CLIQUE to CLIQUE-or-almost.

Start with the graph $G=(V,E)$ in the instance of CLIQUE and build a graph $G'$ in which there are two copies $v_1, v_2$ of each vertex $v \in V$ along with the edge $(v_1, v_2)$. For each $(u,v) \in E$ add to $G'$ the four edges $(u_1, v_1), (u_1, v_2), (u_2, v_1), (u_2, v_2)$.

If there is a clique $C$ of size $k$ in $G$ then there is a clique of size $2k$ in $G'$ (consider all the copies of the vertices in $C$).

If there is a clique $C$ of size $2k$ in $G'$ then there is a clique of size at least $k$ in $G$ (consider all the vertices $v \in V$ such that $C$ contains at least one of $v_1$ and $v_2$).

Finally, if there is a clique $C$ minus one edge $(u_i ,v_j)$ of size $2k$ in $G'$, then $C$ cannot contain $v_{3-j}$, as otherwise the edge $(u_i, v_{3-j})$ would be missing too. This means that $C \setminus \{v_j\}$ contains $2(k-1)+1$ vertices. Thus, the set of vertices $w$ such that $C \setminus \{v_j\}$ contains at least one of $w_1$ and $w_2$ is a clique of size at least $k$ in $G$.

| cite | improve this answer | |
  • $\begingroup$ See my comment to @Yuval Filmus, $\endgroup$ – user3343396 Nov 7 '19 at 19:36
  • $\begingroup$ Are you fine with a Cook reduction? If so, check if $G = (V,E)$ has a clique, if the answer is "yes" then you are done. If not, for each edge $e$ that is missing from $E$, check if $G + e$ contains a clique. If the answer is "yes" then you found an almost-clique in $G$. If all the answers are "no", then the answer to your problem is also "no". If you want a Karp-reduction, take the disjoint union $G'$ of $G$ with all graphs $G+e$ for $e \not\in E$. There is an almost-clique in $G$ iff there is a clique in $G'$. $\endgroup$ – Steven Nov 7 '19 at 19:44
  • $\begingroup$ I can't use a Cook reduction, because if there exist a Cook reduction from A to B, that doesn't mean that there must be a Karp reduction from A to B. Am i wrong? $\endgroup$ – user3343396 Nov 8 '19 at 8:05
  • $\begingroup$ You are right but I also provided a Karp reduction. $\endgroup$ – Steven Nov 8 '19 at 8:07
  • $\begingroup$ You are right! thanks! please update your answer $\endgroup$ – user3343396 Nov 8 '19 at 13:50

Here is a reduction from CLIQUE to CLIQUE-or-almost.

Let $G$ be an arbitrary graph. Form a new graph $G'$ by adding two new vertices $x,y$ connected to all vertices of $G$, but not to each other. If $G$ contains a $k$-clique, then $G'$ contains a $(k+2)$-clique with a missing edge.

Conversely, suppose that $G'$ contains a $(k+2)$-clique $S$, possibly with a missing edge. If the clique doesn't contain a missing edge, then $S \setminus \{x,y\}$ is a clique of size at least $k$ in $G$. If $x,y \in S$ then the missing edge is $(x,y)$, and again $S \setminus \{x,y\}$ is a $k$-clique of $G$. In the remaining case, $|S \setminus \{x,y\}| \geq k+1$. Remove one vertex from the missing edge to obtain a clique of size at least $k$ in $G$.

For a reduction in the other direction, it is well-known that CLIQUE is NP-hard. Since CLIQUE-or-almost is clearly in NP, by definition there is a reduction from CLIQUE-or-almost to CLIQUE. One can construct such a reduction via the proof of the Cook-Levin theorem.

| cite | improve this answer | |
  • $\begingroup$ If i'm not wrong, you described a reduction from clique to clique-or-almost. as i mentioned in the post, i am seeking for a "reduction from Clique-or-almost to Clique". $\endgroup$ – user3343396 Nov 7 '19 at 19:35
  • $\begingroup$ Clique is known to be NP-hard, so we know that such a reduction exists. There is no reason to construct such a reduction explicitly. $\endgroup$ – Yuval Filmus Nov 7 '19 at 19:38
  • $\begingroup$ I know but i need to prove that Clique-or-almost is in NP by showing a direct reduction to Clique. $\endgroup$ – user3343396 Nov 7 '19 at 21:53
  • $\begingroup$ You can prove that it's in NP directly. It's much easier. $\endgroup$ – Yuval Filmus Nov 7 '19 at 21:57
  • 1
    $\begingroup$ Sounds like a silly exercise. $\endgroup$ – Yuval Filmus Nov 8 '19 at 8:06

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.