0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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$

$\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.