2
$\begingroup$

I am reading a book about complexity analysis and cannot find a way to solve a problem in that book. The problem is, that I do not understand how to determine the smallest possible parameters, given the runtime of an algorithm. Do I just need to insert some numbers and see if the parameters exceed n at some point? Perhaps someone can explain that to me.

Consider the following exercise:

The following O(.) expressions represent worst-case runtimes of different algorithms, where n is a measure of the input size and p, q and r are parameters (where p, q, r <= n). Which of the following running times are FPT running times? Give the smallest possible parameter set for which the running times are FPT (if one exists) and explain.

a) $O(p^q * n^2)$

Now I know that by the definition of FPT, this runtime is FPT (because we have a function of the parameters times n^constant). However, what are the smallest $p$ and $q$ in that case?

There are some more, but I just want to understand how to solve it and then I'll try the rest myself again.

Taken from:

Rooij, I. V., Blokpoel, M., Kwisthout, J., & Wareham, T. (2019). Fixed-Parameter Tractable Time. In Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis (p. 125). Cambridge, England: Cambridge University Press.

$\endgroup$
0
$\begingroup$

Recall that the runtime must be of the form $f(k) \cdot n^c$ for some constant $c$. So I believe that the exercise is asking, given that all three are at most $n$, which do you have to take as formal parameters in your analysis to achieve an FPT runtime.

So if only $p$ is a parameter, is that FPT? What if only $q$? Clearly, if both are fixed, you have FPT runtime.

$\endgroup$
  • $\begingroup$ Thank you for your help! I really did not understand that from the exercise. That makes it a lot easier for me. I thought I really had to calculate the parameters. $\endgroup$ – The G May 26 at 21:44

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.