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?

  • 5
    $\begingroup$ 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). $\endgroup$ 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.

  • 2
    $\begingroup$ 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) $\endgroup$
    – Vor
    Oct 23 '13 at 8:43
  • $\begingroup$ 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. $\endgroup$ Oct 23 '13 at 12:08
  • $\begingroup$ 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$. $\endgroup$
    – Parham
    Oct 25 '13 at 16:01
  • 1
    $\begingroup$ @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. $\endgroup$ 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.

  • $\begingroup$ David, I followed your comment... $\endgroup$ Oct 23 '13 at 5:21
  • $\begingroup$ 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! :-) $\endgroup$ Oct 23 '13 at 11:13

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.