Parameterized vertex cover on $r$-regular graphs I am trying to solve the following exercise from this book:


  Show that CLIQUE PROBLEM, parameterized by the solution size $k$, is
  Fixed-parameter tractable (FTP) on $r$-regular graphs for every
  fixed integer $r$.


Here, the CLIQUE PROBLEM is given a instance $(G, k)$, decide whether $G$ has a clique of size $k$ or not.

First of all, for an instance $(G, k)$,  if $k &gt; r+1$, then the answer is NO, because each vertex is connected with exactly $r$ elements, the maximum size of a clique is $r + 1$ (vertex plus $r$ neighbours). So, we can assume that $k \le r+1$.

Let $N(v)$ be the set of neighbours of $v$.

I thought of that simple algorithm

.... for each vertex $v \in V(G)$

........ check if for any subset $X \subset N(v)$, such that $|X| = k - 1$, $X \cup \{v\}$ is a clique.

Since there is only $\binom r k$ such subsets $X$ for each vertex and we take time polynomial in $k$ to check if $X \cup \{v\}$ is a clique, then, this algorithm is already a FTP and is of the form $\left( k^{O(1)}\binom{r}{k} \right)n$.

If everything is right, them I have solved the exercise. However, the next thing I have to do in the exercise, is to show that this problem is also a FTP considering the parameter $k + r$ (so, $r$ is no longer seen as a constant), and the same algorithm works in this case. Since I was expecting to face a harder exercise in this case of $k + r$, I started to think my solution is not right.

So, what is wrong?
There's nothing wrong with your solution, the exercise is just easier than you expected.

Your analysis correct, apart from missing out the $-1$, so it should be $k^{\mathcal{O}(1)}\cdot\binom{r}{k-1}\cdot n$, which is, of course, of the required form $f(k+r)\cdot n^{\mathcal{O}(1)}$, and the $-1$ doesn't really change anything.

The biggest mistake is writing $\mathrm{FTP}$ instead of $\mathrm{FPT}$. The first is a protocol, the second is a complexity class.

Moving to pure speculation, I would guess the authors were, in the second part, simply looking for reinforcement of the difference between $\mathrm{FPT}$ and in class $\mathrm{X}$ for every fixed value of some parameter (in this case, something like $f(k)\cdot n^{r}$ would work for the first part of the exercise, but not the second. The Hitting Set problem, as an example, has such an algorithm, where the parameter $k$ is the size of the solution, and $r$ is the size of the input sets; it's in $\mathrm{FPT}$ for every fixed $r$, but not in $\mathrm{FPT}$ for parameter $k+r$).