# 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 > 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?

• Could you specify exactly what the problem is when the parameter is $k+r$? I'm confused; of course no $r$-regular graph has a clique of size $k+r$. Is $k+r$ a constant? I'm sorry if this is a silly question. Commented Sep 29, 2016 at 23:09
• @LieuweVinkhuijzen the problem is the same, which means we still have to decide if there is a clique of size $k$. However, now we have to decide it in time $O(f(k + r) poly(n))$ instead of $O(f(k)poly(n))$ (with $r$ seen as a constant). Commented Sep 30, 2016 at 0:58

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$).

Your answer is correct, since your algorithm indeed runs in time $$\binom{r}{k}n$$.

Let us go the extra mile and take a moment to think about the worst case input to your algorithm, and see if we can manage to write the running time as $$f(r)n$$ or $$f(p)n$$, to show that the algorithm is FPT. Of course, this is not necessary to determine that the problem is FPT, it is just a sanity check, say, to see if there are any surprises: if the algorithm is FPT then it must also be FPT on the hardest instances.

The case when $$r$$ is fixed. In this case, the worst case for $$\binom rk$$ is when $$k=\frac 12r$$, in which case $$\binom rk=\binom r{\frac 12r}n\approx 2^{r}\frac 1{\sqrt r}n$$. Indeed, we can write this as $$f(r)n$$ with $$f(r)=2^r/\sqrt r$$, so the algorithm is FPT.

The case when $$r+k=p$$ is fixed. Some math shows that the worst case is when $$r$$ takes the value $$r=\left(\frac 12+\frac 1{2\sqrt 5}\right)p\approx 0.724p, \quad \text{ so }k\approx 0.276p$$ The running time of your algorithm becomes $$\binom{0.724p}{0.276p}n$$. If we write $$f(p)=\binom{0.724p}{0.276p}\approx 1.62^p$$, then the running time of the algorithm is $$f(p)n$$, so the problem is FPT.

• Are you sure about the second paragraph? Can you justify it? If $r$ is fixed, then yes, $\binom{r}{k}$ is maximized by $k=r/2$. However, when $r$ is not fixed and instead we have $k+r=p$, then is that still the maximizer? It's not clear to me, but I'm skeptical. One approximation is $\binom{r}{k} \sim 2^{r \cdot h_2(k/r)}$, where $h_2(\cdot)$ is the binary entropy function. It should be possible to compute the maximum from there by differentiating and using calculus.
– D.W.
Commented Sep 30, 2016 at 16:30
• @D.W. You are right: the value $\binom rk$ reaches its maximum when $r=\left(\frac 12+\frac 1{2\sqrt 5}\right)p$, not when $r=\frac 23p$. I have edited my answer above. Better late than never! Commented Mar 10 at 14:46