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) \not\in 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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Hint: find a polynomial function which transforms finding near clique instance to any other NP-complete problem instance, and vice versa. $\endgroup$– Bartosz PrzybylskiMar 17, 2013 at 7:34
-
1$\begingroup$ @Bartek: what the OP needs is to find a reduction from an NP complete problem to near-clique, not vice-versa. By the way, it is easy to construct a Turing-reduction (that is, to use an oracle for near-clique) to solve CLIQUE. This shows that if near-clique is in $P$, then $P=NP$, but it doesn't show $NP$-completeness. $\endgroup$– ShaullMar 17, 2013 at 9:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
