2
$\begingroup$

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?

$\endgroup$
1
  • 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, 2013 at 14:02

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
4
  • 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, 2013 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, 2013 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, 2013 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, 2013 at 0:18
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ David, I followed your comment... $\endgroup$ Oct 23, 2013 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, 2013 at 11:13
0
$\begingroup$

A much simpler and cruder reduction based on the same idea of the accepted answer:

On an instance of NEAR-CLIQUE $\langle G,k\rangle$, duplicate $G$ by at most $|V|^2$ times. Do not add any edges between the copies. Then, for each missing edge in $G$, choose one copy that has not been chosen and add that edge to the copy (each copy should only has one edge added). Return $\langle G',k\rangle$, where $G'$ is our modified graph, and $k$ is the same $k$ from the input.

This process takes polynomial time, because copying the graph takes linear time and we are doing it for at most $|V|^2$ times.

Suppose $\langle G,k\rangle \in$ NEAR-CLIQUE, then one of the copies of $G$ in $G'$ should contain a k-clique by the definition of NEAR-CLIQUE. Hence $\langle G',k\rangle \in$ CLIQUE.

Suppose $\langle G',k\rangle\in$ CLIQUE, then, if $G$ itself already contains a k-clique in the first place, $\langle G,k\rangle\in$ NEAR-CLIQUE by definition; if not, then this k-clique must be the result of us adding one extra edge to one of the copies of $G$. This, by construction, means that adding one edge somewhere in $G$ would give us a k-clique. Therefore $\langle G,k\rangle\in$ NEAR-CLIQUE.

$\endgroup$
2
  • $\begingroup$ "If $G$ itself already contains a $k$-clique in the first place, $\langle G,k\rangle\in$ NEAR-CLIQUE by definition". That is not correct. In fact, a $k$-clique in $G$ is never a near $k$-clique in $G$. $\endgroup$
    – John L.
    Dec 8, 2022 at 4:14
  • $\begingroup$ @JohnL. Nice catch. This would only work if the language definition does not require the edge being added to be part of the clique. Thanks for pointing that out! (I wonder if there is an easy fix for this though?) $\endgroup$
    – aquila_zyy
    Dec 8, 2022 at 23:38

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.