World's most popular travel blog for travel bloggers.

# [Solved]: Direct reduction from Near-Clique to Clique

, ,
Problem Detail:

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?

#### Answered By : Luke Mathieson

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.