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$
  • $\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$ – Lieuwe Vinkhuijzen Sep 29 '16 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$ – Hilder Vitor Lima Pereira Sep 30 '16 at 0:58
1
$\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$
0
$\begingroup$

Your algorithm runs in time $\binom{r}{k}n$. For a given value of $k+r$, what is the worst combination of $k,r$ that your algorithm could encounter? What is the time complexity of your algorithm on that input?

I happen to know that $\binom{r}{k}$ is maximized when $k=\frac{1}{2}r$, which is when the there is the greatest number of ways to pick $k$ neighbours from $r$. So your algorithm runs slowest, for a given $k+r=p$, when $k=\frac{1}{3}p$, in which case it runs in $\binom{{\small\frac{2}{3}}p}{{\small\frac{1}{3}}p}n$, so the function you are looking for is $f(k+r)=\binom{{\small\frac{2}{3}}p}{{\small\frac{1}{3}}p}$.

$\endgroup$
  • 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 '16 at 16:30

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.