Finding a clique $C$ in an undirected graph $G= (V, E)$ such that $|C| > |V|/2$ is in P or NP-hard? How can I prove it?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Given a graph $G=(V, E)$, the problem of finding a clique $C$ with $|C| \ge \frac{|V|}{2}$ is a search problem and, as such, is neither in $\mathsf{P}$ nor in $\mathsf{NP}$ since $\mathsf{P} \subseteq \mathsf{NP}$ and $\mathsf{NP}$ only contains decision problems.
