# Prove “almost clique” is NP complete

Given $G=(V,E)$, undirected graph, a group of vertices $S$ is called almost clique if by adding a single edge, $S$ becomes a clique.

Consider the language: $L=\{\langle G,t\rangle \mid \text{the graph $$G$$ contains a $$t$$-sized almost-clique}\}$. Prove that $L$ is NP-complete.

Obviously, it is solved by polynomial reduction, but is it from Clique or 3SAT? And how?

• The easiest reduction is problem from clique, but you can always reduce from any NP-complete problem. As to how, that is for you to figure out. – Yuval Filmus Jun 10 '17 at 12:17
• What did you try? Where did you get stuck? The point of doing exercises such as this one is to get used ot doing reductions and figuring it out for yourself. Being told the answer isn't really going to help you, since you can find hundreds of examples of reductions in textbooks and on the web already. You don't need any more examples: you need to learn how to produce your own reductions. – David Richerby Jun 10 '17 at 17:39
• There is also reduction from 3-SAT that can be found here. – Tegra Morgan Jun 12 '17 at 5:29

You can reduce to this from $CLIQUE$.

Given a graph $G=(V,E)$ and $t$, construct a new graph $G^*$ by adding two new vertices $\{v_{n+1},v_{n +2}\}$ and connecting them with all of $G$'s vertices but removing the edge $\{v_{n+1},v_{n+2}\}$, i.e. they are not neighbors in $G^*$. return $G^*$ and $t+2$.

If $G$ has a $t$ sized clique by adding it to the two vertices we get an $t+2$ almost clique in $G^*$ (by adding $\{v_{n+1},v_{n+2}\}$).

If $G^*$ has a $t+2$ almost clique we can look at three cases:

1) It contains the two vertices $\{v_{n+1},v_{n+2}\}$, then the missing edge must be $\{v_{n+1},v_{n+2}\}$ and this implies that the other $t$ vertices form a $t$ clique in $G$.

2) It contains one of the vertices $\{v_{n+1},v_{n+2}\}$, say w.l.o.g. $v_{n+1}$, then the missing edge must be inside $G$, say $e=\{u,v\}\in G$. If we remove $u$ and $v_{n+1}$ then the other $t$ vertices, which are in $G$ must form a clique of size $t$.

3) It does not contain any of the vertices $\{v_{n+1},v_{n+2}\}$, then it is clear that this group is in $G$ and must contain a clique of size $t$.

It is also clear that the reduction is in polynomial time, actually in linear time, log-space.

• This is a nice answer but you it looks an awful lot like you just did somebody's homework for them. – David Richerby Jun 10 '17 at 18:57

The subgraph $S$ of $G=(V,E)$ is a called an $s$-defective clique when $E(G[S]) \geq \binom{|S|}{2} - s$, i.e., missing at most $s$ edges from clique. Your definition is similar to 1-defective clique.

The question about hardness can be done in one line. Observe, that defective clique is a hereditary structure. By Yannakakis theorem its optimization maximum problem is NP-hard.