# Clique-or-almost reduction to clique

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}\}.$$

• 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. Nov 7, 2019 at 17:48
• I added a formal definition for Clique-or-almost. Near-clique is the same but without the work "possibly". Nov 7, 2019 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$$.

• See my comment to @Yuval Filmus, Nov 7, 2019 at 19:36
• 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'$. Nov 7, 2019 at 19:44
• 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? Nov 8, 2019 at 8:05
• You are right but I also provided a Karp reduction. Nov 8, 2019 at 8:07

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.

• 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". Nov 7, 2019 at 19:35
• 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. Nov 7, 2019 at 19:38
• I know but i need to prove that Clique-or-almost is in NP by showing a direct reduction to Clique. Nov 7, 2019 at 21:53
• You can prove that it's in NP directly. It's much easier. Nov 7, 2019 at 21:57
• Sounds like a silly exercise. Nov 8, 2019 at 8:06