3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Hint: find a polynomial function which transforms finding near clique instance to any other NP-complete problem instance, and vice versa. $\endgroup$ – Bartosz Przybylski Mar 17 '13 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$ – Shaull Mar 17 '13 at 9:02
7
$\begingroup$

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.

$\endgroup$

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.