# in a graph G= (V,E), finding a clique of size |V|- d where d is some constant

Is the question above still NP? I've been stuck on this question for couple of days now... I know k-Clique problem is NP-complete generally, but the problem is k = |V|-d where d is some integer constant...My current guess is that for large |V|, d << |V| => Finding all subsets of size k = (V choose V-d) so this question is in P.

• Great, you have a guess. The next step is to try to prove your guess. That's how we know whether our guesses are correct. Have you given that a try? Have you made any progress so far? – D.W. Dec 11 '17 at 4:34

The brute force algorithm would check all vertex subsets of size $n-d$, where $|V|=n$. There are $$\binom{n}{n-d} = \binom{n}{d}=\frac{n(n-1)\dots (n-d+1)}{d!}$$ different subsets. This quantity is $\mathcal{O}(n^d)$ and since $d$ is constant this problem is in $P$.

Is the question above still NP?

Even though the problem is in $P$, this problem is still in $NP$ since $P \subseteq NP$, however, unlike $k$-clique problem this problem may not be NP-complete.