How to find parameter sets for a big-O expression to be fixed-parameter tractable?

Question

I've been stuck on the following assignment taken from Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis:

Imagine that the following big-O expressions correspond to the worst-case running times of different algorithms, where $n$ denotes the input size and $p$, $q$ and $r$ are potential parameters (for which we assume that $p, q, r \leq n$). Which of these can be made to conform to the requirements of fixed-parameter tractability? Either give the smallest possible set of parameters for which this is the case (and show that it is indeed the smallest), or argue why $p$, $q$ and $r$ are not suitable parameters for this.

Specifically, I'm trying to find the smallest set of parameters for the following big-O expression:

$O(p^r\sqrt{q}n^2)$

I have looked at an older thread by The G - Determine smallest possible parameter set for FPT where the same question is asked for $O(p^q*n^2)$. From the answer to that thread I can derive that the smallest possible set of parameters which conform to the requirements is $\{p,q\}$. However I feel like this conflicts with the definition of FPT by Wikipedia where it says

The crucial part of the definition is to exclude functions of the form $f(n,k)$ such as $n^k$.

from which I would assume that it is not possible for a problem in FPT to have two parameters of which the one is a polynomial of the other.

Personally I'm stuck with figuring out how FPT works with multiple parameters. Am I right in thinking that the smallest set which satisfies the requirements of FPT of my problem is $\{q\}$ (since it is consistent with the definition $FPT = O(f(k)*|x|^{O(1)})$)?

Answer 1

Here is a simple method to find the parameters with respect to which (the problem whose worst runtime is bounded by) a big $O$-expression becomes fixed-parameters tractable (FPT), i.e., bounded by a product of some polynomial of the input size $n$ and a function that depends only on those parameters.

For example, $p^r\sqrt{q}n^2$, where $n$ is the input size.

Is it tractable if the fixed parameters are $\{p\}$?
Replace all other parameters with $n$. You get $p^n\sqrt{n}n^2$, where the term $p^n$ can be not expressed as a product of a function of $p$ and a function of $n$. In fact, $p^n$ cannot be bounded by such a product.

Is it tractable if the fixed parameters are $\{r\}$?
Replace all other parameters with $n$. You get $n^r\sqrt{n}n^2$, where the term $n^r$ can be not be expressed as a product of a function of $r$ and a function of $n$. In fact, $n^r$ cannot be bounded by such a product.

Is it tractable if the fixed parameters are $\{p, r\}$?
Replace all other parameters with $n$. You get $p^r\sqrt{n}n^2$, which can be seen as the product of $p^r$ and $\sqrt nn^2$. The former, $p^r$ is a function that depends on the selected parameters only. The latter, $\sqrt nn^2$ is a function of $n$ that grows slower than $n^3$ (or, in fact, a "polynomial" function by itself). So $\{p,r\}$ is a valid choice.

Is it tractable if the fixed parameters are $\{q\}$?
Replace all other parameters with $n$. You get $n^n\sqrt{r}n^2$, where the term $n^n$ is independent of $q$ and not bounded by a polynomial of $n$. Hence, $\{q\}$ is not a valid choice.