1
$\begingroup$

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)})$)?

$\endgroup$
5
  • 2
    $\begingroup$ Please credit the original source of all copied material: cs.stackexchange.com/help/referencing. Thank you! $\endgroup$
    – D.W.
    May 16 at 21:05
  • $\begingroup$ Can you articulate a single specific conceptual question that you'd like answered? Preferably, one that will be useful even to others who aren't working on exactly the same exercise. I see multiple questions, both explicit (I see two of them) and implicit (perhaps you are implicitly asking us to check each assumption, of which there are multiple). Our site works best if you ask a single question per post. I don't know what you mean by "possible parameter" or "obsolete" or "FPT = ...". $\endgroup$
    – D.W.
    May 16 at 21:08
  • $\begingroup$ @D.W. fixed it, thanks for the info! $\endgroup$
    – sebas2201
    May 16 at 21:15
  • $\begingroup$ I don't see appropriate attribution for copied materials. I don't see a conceptual question that will be useful to others who aren't working on the same exercise. We generally discourage "please check whether my answer is correct" questions, as answers are unlikely to be useful to others in the future. Perhaps you want to ask what is the definition of FPT when there are two parameters? $\endgroup$
    – D.W.
    May 16 at 21:31
  • $\begingroup$ @D.W. Three parameters even. I'm not sure whether I can formulate the definition of FPT as a 3-parameter problem $f(p,q,r)=p^r\sqrt{q}$ or two seperate functions ($f(p,r)=p^r$, $f(q)=\sqrt{q}$). Also, could you clarify what is incomplete about the attribution for the copied material? I have provided the name and link to the post of the original author. I left out the quote since I'm referring to the big-O expression they used. $\endgroup$
    – sebas2201
    May 16 at 21:54

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I wasn't aware that you could replace the non-fixed parameters with $n$. This makes sense though since these parameters are either smaller than or equal to $n$. This really helped me understand the concept. Thanks! $\endgroup$
    – sebas2201
    May 17 at 7:24

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.