2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.