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?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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:
- Since vertices of independent set have degree at most $k$, we first remove from $G$ all vertices whose degree is more than $k$.
- There are now only $k^2$ edges in the current graph.
- 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)$.
- 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.
