Is $k$-CLIQUE W[1]-hard for parameter $n - k$?

Question

It is well-known that the problem of deciding if a graph contains a clique of size $k$ is W[1]-hard with respect to parameter $k$.

Is it also known to W[1]-hard (or perhaps FPT) in parameter $n - k$, where $n$ is the number of vertices of the graph?

Answer 1

I believe this is FPT.

FInding a $(n - k)$-clique is equivalent to finding an independent set of size $n - k$ on the complement. This is equivalent to finding a vertex cover of size $k$. And the latter is FPT.

Answer 2

Following solution works, just replace $k$ with $n-k$, and reverse the graph so that instead of clique we need to search for an independent set.

If the input graph $G$ contains a set $W$ of size at most $k$ for which $V(G)\setminus W$ is independent set, then it can be found in $f(k)\cdot n^{O(1)}$ time as follows:

1. Since vertices of independent set have degree at most $k$, we first remove from $G$ all vertices whose degree is more than $k$.
2. There are now only $k^2$ edges in the current graph.
3. Let $A$ be set of all vertices on which at least one edge is incident, then $V(G)\setminus A$ is an independent set of size at least $(n-2k^2)$.
4. So $W$ must be contained in set $A$ whose size is at most $2k^2$. We can scan over all ${2k^2}\choose{k}$ subsets of A to check removal of which set makes the graph an independent set.