0
$\begingroup$

Given a graph $G$, we say a subset of vertices $S$ is a "good" clique if $S$ itself is a clique and for any vertex $v \in G$, there is a vertex $u \in S$ such that $v$ is adjacent to $u$. I'd like to ask whether determining if there exists a "good" clique of size $k$ is NP-complete or not.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Finally, I figure out the mapping reduction from the standard k-clique problem. For any instance of k-clique problem, i.e., finding a clique in graph $G$ with size at least $k$, we copy $G$ into $G'$, add a super vertex connecting to all vertices in $G'$ and ask to find a "good" clique of size $k+1$ in $G'$. There is a clique of size at least $k$ in $G'$ iff there is a "good" clique of size at least $k+1$ in $G'$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .