1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Sep 29, 2016 at 23:09
  • $\begingroup$ @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). $\endgroup$ Sep 30, 2016 at 0:58

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Sep 30, 2016 at 16:30
  • $\begingroup$ @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! $\endgroup$ Mar 10 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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