Direct reduction from Near-Clique to Clique

An undirected graph is a Near-Clique if adding one more edge would make it a clique. Formally, a graph $G=(V,E)$ contains a near-clique of size $k$ if there exists $S\subseteq V$ and $u,v\in S$ where $|S|=k$, $(u,v)\notin E$, and $S$ forms a clique in $(V,E\cup\{(u,v)\})$. How can I show a direct reduction from Near-Clique to Clique?

• Are you sure you want a reduction that way round? Clique is a well-known NP-complete problem and, if you wanted to prove that Near-Clique is NP complete, too, you need a reduction from Clique to Near-Clique (which is the opposite of what you're asking for). – David Richerby Oct 22 '13 at 14:02

Let $(G,k)$ be an instance of Near-Clique, construct an instance $(G',k')$ of Clique as follows.

For each $uv \notin E(G)$, add to $G'$ a subgraph corresponding to $(N(u)\cap N(v))$, i.e.,

1. for each $x \in N(u)\cap N(v)$ add the vertex $x'$ to $V(G')$, and
2. for each edge pair of vertices $x,y \in (N(u)\cap N(v))$ if $xy \in E(G)$ add the edge $x'y'$ to $E(G')$.

Set $k' = k-2$

As $uv \notin E(G)$, $u \notin N(v)$ and $v \notin N(u)$. Note that each of these corresponding subgraphs is disjoint, so a vertex in $G$ may have several corresponding vertices in $G'$.

Now we claim that $(G,k)$ has a $k$-near-clique iff $(G',k'=k-2)$ has a $k'$-clique.

$(\Rightarrow)$ Let $D$ be the vertices of the near clique, then there are two vertices $u,v \in D$ such that

1. $uv \notin E(G)$,
2. $D\setminus\{u,v\}$ forms a clique of size $k-2$, and
3. $D \subseteq N(u)\cap N(v)$ (by definition).

Then $G[D\setminus\{u,v\}]$ (the subgraph induced by $D$) is a subgraph of $G'$ (via the construct and property 3). Therefore by property 2, $G'$ has a clique of size $k-2=k'$.

$(\Leftarrow)$ Let $C'$ be a $k'=k-2$ size clique in $G'$ and let $C$ be the corresponding vertices in $G$ (with induce a $k-2$-clique in $G$ as well). By the construction, there must exist $u,v\in V(G)$ such that $C\subset N(u)\cap N(v)$ (i.e. $u$ and $v$ are adjacent to all the vertices of $C$), moreover $uv \notin E(G)$. Therefore $C\cup\{u,v\}$ forms a $k$-sized near-clique in $G$.

The last step is to just assure ourselves that this is polynomial-time computable. In constructing $G'$, we examine at most each pair of vertices, and compute the intersection of their neighbourhoods. Just so we don't have to think too hard about details, that is at most $n^{2}$ neighbourhoods, and for each we take $O(n^{2})$ time to compute the intersection. So the total construction can be enacted in polynomial-time.

• Does the reduction also work if for every $uv \notin E$ the subgraph added to $G'$ is the node induced subgraph of $G$ induced by $(N(u) \cap N(v)) \cup \{u,v\}$, plus the edge $uv$? (in this case $G'$ has a $k$-Clique iif $G$ has a Near $k$-Clique ... the reduction is a little bit simpler) – Vor Oct 23 '13 at 8:43
• Yes! You are quite right. If $G'$ has a $k$-clique, then either (for some $u,v$) it's from a $k-2$ clique and the new edge (hence a $k$-near-clique in $G$), or it doesn't include at least one of $u$ or $v$, but then we can swap the missing $u$ and/or $v$ with some other vertices in the clique (any, as they all have to be adjacent to $u$ and $v$ in both $G$ and $G'$), and we have the first case again. – Luke Mathieson Oct 23 '13 at 12:08
• it's not clear to me how by construction there must be a pair that contains all vertices in $C$. However, it is clear that there is such pair for each individual vertex $x \in C$. – Parham Oct 25 '13 at 16:01
• @MahmoudAlimohamadi, each disconnected component in $G'$ is made by taking a pair $u$, $v$ in $G$ with no edge between them, and taking the intersection of their neighbourhoods. So everything in the intersection is adjacent to both these vertices. Then in $G'$, if there's a clique, it must be in single component, so all vertices must be adjacent (in $G$) to the two vertices that cause that component to be in $G'$ in the first place. The improvement to the reduction that Vor suggests in the first comment might make this clearer. – Luke Mathieson Oct 26 '13 at 0:18

Hint: Given an instance of clique, add two new vertices $u,v$, and connect each of them to all of the original vertices.

• David, I followed your comment... – Yuval Filmus Oct 23 '13 at 5:21
• Sorry -- you're right. For some reason, I have this huge mental block about the direction of reductions. It's obviously not a good idea for me to comment "You have the reduction the wrong way around" twice in one day! :-) – David Richerby Oct 23 '13 at 11:13