Problem Detail: An undirected graph is a near clique if adding an additional edge would make it a clique. Formally, a graph $G = (V,E)$ contains a near clique of size $k$ where $k$ is a positive integer in $G$ if there exists $S subseteq V$ where $|S| = k$ and $u,v in S$ where $(u,v) notin E$, and $S$ forms a clique in $(V,E cup {(u,v)})$. How can I show finding a near clique of size $k$ in $G$ is NP-complete?
Asked By : idealistikz
Answered By : Shaull
I think the following reduction works (unless I missed something): Given $G=(V,E)$ and $k$, output $G’$ which is obtained from $G$ by adding $2$ new vertices ${x,y}$. that are each connected to all the vertices in $V$ (but not to each other). Finally, the output is to search for a $k+2$ near clique. Clearly this is polynomial (linear). If there exists a $k+2$ near clique in $G’$, then if $k+1$ of its vertices are contained in $V$, then $G$ has a $k$-clique. If less than $k+1$ vertices are from $V$, then at least $k$ of them are, since $x$ and $y$ are not connected between them. But then, the $k$ remaining vertices in $G$ must form a clique. Conversely, if $G$ has a $k$-clique, then just add the two new vertices $x,y$ to get a $k+2$-near clique.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10573
