# Karp hardness of a diameter-decreasing planted clique

A diameter-decreasing planted clique in an undirected graph $$G(V,E)$$ is a set of vertices $$\mathcal{C}\subseteq V$$ such that if we add all the missing edges between any pair of vertices in $$\mathcal{C}$$ to turn it into a clique, then the diameter of the obtained graph $$G'$$ is at most $$2$$.

Diameter-decreasing Planted Clique Problem:

Input: An undirected graph $$G(V,E)$$ and a natural number $$k$$

Output: YES if there exists a diameter-decreasing planted clique of size $$k$$ in $$G$$, otherwise NO

What is the complexity of this problem?

This problem is $$NP$$-complete. Reduce from Exact Cover by $$3$$-Sets (X3C).

Given an X3C instance, its ground set is $$\mathcal{U}=\{e_1,e_2,\cdots,e_n\}$$. Its collecion of $$3$$-subsets is $$\mathcal{C}=\{s_1,s_2,\cdots,s_m\}$$.

For each element in the ground set and each subset in the collection, we create a new vertex (which will be referred to by the same name, henceforth).

For each pair of element $$e_i$$ and subset $$s_j$$ such that $$e_i\in s_j$$, connect the two vertices.

For $$s_j$$'s vertices: Connect all pair of $$s_j$$'s vertices to make these a clique.

Then, create a new vertex $$s$$ and connect it to all $$s_j$$'s vertices.

For $$e_i$$'s vertices: For each pair of elements $$e_{i_1}, e_{i_2}$$ that share no common subset, we create a new vertex $$e_{i_1i_2}$$ and connect it to both of $$e_{i_1}$$ and $$e_{i_2}$$.

Then, create a new vertex $$e$$ and connect it to all $$e_{i_ai_b}$$'s vertices.

Connect $$s$$ and $$e$$ by an edge. Create a new vertex $$t$$ and connect it to both of $$s$$ and $$e$$.

Call the newly constructed graph $$G$$. Set $$k=\frac n3+1$$.

Clearly, we only need to decrease the distance from $$t$$ to each of $$e_i$$'s vertex.

If in the planted clique, we do not choose $$t$$, then for each $$e_i$$, we need to connect it to either $$s$$ or $$e$$. Because $$s$$ and $$e$$ are all the neighbors of $$t$$. That is going to exceed the bound of $$\frac n3+1$$ on the cardinality of the clique.

So, $$t$$ must be included in the planted clique. Denote by $$x$$, $$y$$ and $$z$$ (in this order) the number of vertices included in the planted clique among the $$s_j$$'s vertices, $$e_i$$'s vertices and $$e_{i_ai_b}$$'s vertices (resp.)

We can see that each one in $$x$$ vertices of $$s_j$$'s vertices will decrease the distance from $$t$$ to $$3$$ $$e_i$$'s vertices.

Similarly, each one in $$y$$ vertices of $$e_i$$'s vertices will decrease the distance from $$t$$ to $$1$$ $$e_i$$'s vertices.

And, each one in $$z$$ vertices of $$e_{i_ai_b}$$'s vertices will decrease the distance from $$t$$ to $$2$$ $$e_i$$'s vertices.

So, we must have $$3x+y+2z\geq n$$. But also, $$x+y+z=\frac n3$$.

We deduce that $$x=\frac n3$$ and $$y=z=0$$