<p><strong>(relatively) SHORT ANSWER:</strong></p>
<p>If <span class="math-container">$f'()$</span> is not non-decreasing, either</p>
<ol>
<li>one can define a strictly increasing function <span class="math-container">$g'()$</span> such that <span class="math-container">$f'(g'(k))$</span> is non-decreasing, and apply the result to the function <span class="math-container">$f'(g'())$</span>; or</li>
<li>there is a decreasing function <span class="math-container">$F'(k)$</span> such that <span class="math-container">$f'(k)\leq F'(k) \forall k$</span>, and <span class="math-container">$(Pb,k)\in FPT$</span> implies that <span class="math-container">$Pb\in P$</span>.</li>
</ol>
<p>Assuming that <span class="math-container">$f'()$</span> is non decreasing is equivalent to 1) assuming that <span class="math-container">$Pb$</span> cannot be proven to be in <span class="math-container">$P$</span> so easily (because then it would not make sense to analyze it for FPT) and 2) avoiding defining the function <span class="math-container">$g'()$</span> and a variant <span class="math-container">$Pb'$</span> of <span class="math-container">$Pb$</span> such the function <span class="math-container">$f''()$</span> in the analysis of its complexity is non decreasing. It can be assumed &quot;without loss of generality&quot; and makes the definitions, result statements and proofs considerably shorter and easier to read.</p>
<p><strong>LONGER EXPLANATION:</strong></p>
<p><em>A short introduction:</em></p>
<p>The class of &quot;Fixed Parameter Tractable&quot; (FPT)&quot; problems was introduced in order to refine the class of &quot;Non-deterministic Polynomial time&quot; (NP) problems into smaller classes if difficulty, each class being defined by a parameter <span class="math-container">$k$</span>, which you can think about as a &quot;measure of difficulty&quot;:</p>
<ul>
<li>when <span class="math-container">$k$</span> is unbounded and can get very large, the worst case is bounded only by the size of the instance and the only analysis standing is that of NP problems; whereas</li>
<li>when the value of the parameter <span class="math-container">$k$</span> is bounded, and in particular when it is <strong>fixed</strong>, the problem is said &quot;Fixed Parameter Tractable&quot; if there exists an algorithm which running time is polynomial in the size of the input (e.g. an algorithm running in time within <span class="math-container">$O(n^{k})$</span> would be polynomial for fixed or bounded values of <span class="math-container">$k$</span> but not in general if <span class="math-container">$k$</span> can depend on <span class="math-container">$n$</span>).</li>
</ul>
<p>Formally, the pair <span class="math-container">$(*Pb,k)$</span> formed by a problem <span class="math-container">$Pb$</span> and a parameter <span class="math-container">$k$</span> is within <span class="math-container">$FPT$</span> if there exists an algorithm solving <span class="math-container">$Pb$</span> which runs in polynomial time in the size <span class="math-container">$|x|$</span> of the input <span class="math-container">$x$</span> for any fixed value of <span class="math-container">$k$</span>. That includes running times within <span class="math-container">$O(f(k)\times p(|x|))$</span> for any polynomial <span class="math-container">$p()$</span> and <strong>any</strong> function <span class="math-container">$f()$</span>.</p>
<p><em>Answering the question:</em></p>
<p>The notion of FPT is useless if <span class="math-container">$f()$</span> is non decreasing:</p>
<ul>
<li>as a warming up example, consider the case where <span class="math-container">$f(k)$</span> would be <strong>decreasing</strong>: if a pair <span class="math-container">$(Pb,k)\in FPT$</span> with such a function <span class="math-container">$f(k)$</span>, then <span class="math-container">$Pb$</span> can be solved in polynomial time for any value of <span class="math-container">$k$</span>, so there is no need to consider the parameter <span class="math-container">$k$</span> to refine its analysis beyond <span class="math-container">$P$</span>.</li>
<li>more generally, consider the case where <span class="math-container">$f(k)$</span> is locally decreasing on some intervals, but that there is a strictly increasing integer function <span class="math-container">$g()$</span> such that <span class="math-container">$f(g(k))$</span> is non decreasing: while being able to solve <span class="math-container">$Pb$</span> faster for some particular values of <span class="math-container">$k$</span> might be interesting in practice, in theory we are interested in solving it faster all the time (now knowing what future instances will look like), so we focus on the parts where <span class="math-container">$f()$</span>
is non decreasing and, &quot;without loss of generality&quot;, just assume that <span class="math-container">$f()$</span> is non decreasing to avoid having to introduce the function <span class="math-container">$g()$</span>.</li>
</ul>

CC BY-SA 4.0
2022-08-22T12:38:29.090Z
I will read it word by word tonight after showering. Thank you first for this detailed explain, this afternoon, I got some simple explain from another book which is called "Parameterized Algorithm", I will share it with you later.

I guess i am lacking of some knowledge on computational analysis, some terms are not familiar to me. And it makes it hard to understand the book "Parameterized Complexity Theory" on the first chapter.

Thanks!
Edee
CC BY-SA 4.0
2022-08-22T12:50:34.500Z
You are making it way too complicated, and I’m sure this not what the authors meant. Simply, if $\mathbb A'$ decides $(Q',\kappa')$ in time (at most) $f'(k')\cdot p'(|x'|)$, it also decides it in time $f''(k')\cdot p'(|x'|)$, where $f''(k')=\max\{f'(n):n\le k'\}$ is nondecreasing. Thus, without loss of generality, we may assume $f'=f''$, i.e., that $f'$ is already nondecreasing.
Emil Jeřábek
CC BY-SA 4.0
2022-08-22T11:47:04.117Z
2022-08-22T11:47:04.117Z
J.y B.y
<p>I am trying to understand how this proof works</p>
<p><a href="https://i.sstatic.net/kgYMd.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/kgYMd.png" alt="enter image description here" /></a></p>
<p>I don't understand, why this f' is nondecreasing? What kind of generality makes us come up with such kind of assumption?</p>
<p>Please, I am weak.</p>

CC BY-SA 4.0
2022-08-22T09:31:39.587Z
It would be easier to discuss your question if you included enough context. For example, what is the paper you are screenshotting?
Martin Berger
CC BY-SA 4.0
2022-08-22T12:54:40.730Z
This is not a research-level question. It should have been asked on https://cs.stackexchange.com rather than here.
Emil Jeřábek
CC BY-SA 4.0
2022-08-22T15:48:04.463Z
I already asked at CS stack, they told me to relocate here. @EmilJeřábek , I know the question seems stupid, but I also don't think it could be easily answered in the right way by some prof. or A/prof.
Edee
CC BY-SA 4.0
2022-08-22T16:51:29.293Z
It certainly can be answered easily in the right way. I gave a one-sentence answer in a comment below.
Emil Jeřábek
CC BY-SA 4.0
2022-08-22T17:05:44.963Z
oh, yes, I just saw it. It is what I meant to ask. It's kinda clear and straightforward to answer this stupid question. I don't know why I asked about 'generality'. I guess it's because I don't really familiar with those terms and idioms in the area of computational analysis. If there are any good resources you can recommend, I am here to listen. I started my research one month ago. Thanks. @EmilJeřábek
Edee
CC BY-SA 4.0
2022-08-22T17:30:57.663Z
If you are unfamiliar with the “without loss of generality” idiom, see https://en.wikipedia.org/wiki/Without_loss_of_generality . I am not an expert in computational analysis, but generally speaking, you become familiar with terms and idioms in a particular field by reading more and more papers and books on the topic, it requires time and patience. It’s not that you could just read a glossary and suddenly understand everything.
Emil Jeřábek
CC BY-SA 4.0
2022-08-22T17:39:14.127Z
Thank you so much for this, sir. Appreciate it.
Edee
CC BY-SA 4.0
2022-08-22T19:42:27.793Z
Can you provide any link to where you received that feedback on CS.SE?  It doesn't appear that you have asked any questions from your account on CS.SE.
D.W.
<ds.algorithms><reductions><fixed-parameter-tractable>
Need more explaination on this 'generality'
Edee
# Need more explaination on this 'generality'

(Asked by: username_0 on 2022-08-22)

I am trying to understand how this proof works

[![enter image description here](https://i.sstatic.net/kgYMd.png)](https://i.sstatic.net/kgYMd.png)

I don't understand, why this f' is nondecreasing? What kind of generality makes us come up with such kind of assumption?

Please, I am weak.

**Tags:** ds.algorithms, reductions, fixed-parameter-tractable

> **Comments:**
> **username_1**: It would be easier to discuss your question if you included enough context. For example, what is the paper you are screenshotting?  
> **username_2**: This is not a research-level question. It should have been asked on https://cs.stackexchange.com rather than here.  
> **username_0**: I already asked at CS stack, they told me to relocate here. @EmilJeřábek , I know the question seems stupid, but I also don't think it could be easily answered in the right way by some prof. or A/prof.  
> **username_2**: It certainly can be answered easily in the right way. I gave a one-sentence answer in a comment below.  
> **username_0**: oh, yes, I just saw it. It is what I meant to ask. It's kinda clear and straightforward to answer this stupid question. I don't know why I asked about 'generality'. I guess it's because I don't really familiar with those terms and idioms in the area of computational analysis. If there are any good resources you can recommend, I am here to listen. I started my research one month ago. Thanks. @EmilJeřábek  
> **username_2**: If you are unfamiliar with the “without loss of generality” idiom, see https://en.wikipedia.org/wiki/Without_loss_of_generality . I am not an expert in computational analysis, but generally speaking, you become familiar with terms and idioms in a particular field by reading more and more papers and books on the topic, it requires time and patience. It’s not that you could just read a glossary and suddenly understand everything.  
> **username_0**: Thank you so much for this, sir. Appreciate it.  
> **username_3**: Can you provide any link to where you received that feedback on CS.SE?  It doesn't appear that you have asked any questions from your account on CS.SE.  

---

## 1 answers

### Answer by username_4 on 2022-08-22. Score: -2 | Accepted answer

**(relatively) SHORT ANSWER:**

If $f'()$ is not non-decreasing, either

1. one can define a strictly increasing function $g'()$ such that $f'(g'(k))$ is non-decreasing, and apply the result to the function $f'(g'())$; or
2. there is a decreasing function $F'(k)$ such that $f'(k)\leq F'(k) \forall k$, and $(Pb,k)\in FPT$ implies that $Pb\in P$.

Assuming that $f'()$ is non decreasing is equivalent to 1) assuming that $Pb$ cannot be proven to be in $P$ so easily (because then it would not make sense to analyze it for FPT) and 2) avoiding defining the function $g'()$ and a variant $Pb'$ of $Pb$ such the function $f''()$ in the analysis of its complexity is non decreasing. It can be assumed "without loss of generality" and makes the definitions, result statements and proofs considerably shorter and easier to read.

**LONGER EXPLANATION:**

*A short introduction:*

The class of "Fixed Parameter Tractable" (FPT)" problems was introduced in order to refine the class of "Non-deterministic Polynomial time" (NP) problems into smaller classes if difficulty, each class being defined by a parameter $k$, which you can think about as a "measure of difficulty":

* when $k$ is unbounded and can get very large, the worst case is bounded only by the size of the instance and the only analysis standing is that of NP problems; whereas
* when the value of the parameter $k$ is bounded, and in particular when it is **fixed**, the problem is said "Fixed Parameter Tractable" if there exists an algorithm which running time is polynomial in the size of the input (e.g. an algorithm running in time within $O(n^{k})$ would be polynomial for fixed or bounded values of $k$ but not in general if $k$ can depend on $n$).

Formally, the pair $(\*Pb,k)$ formed by a problem $Pb$ and a parameter $k$ is within $FPT$ if there exists an algorithm solving $Pb$ which runs in polynomial time in the size $|x|$ of the input $x$ for any fixed value of $k$. That includes running times within $O(f(k)\times p(|x|))$ for any polynomial $p()$ and **any** function $f()$.

*Answering the question:*

The notion of FPT is useless if $f()$ is non decreasing:

* as a warming up example, consider the case where $f(k)$ would be **decreasing**: if a pair $(Pb,k)\in FPT$ with such a function $f(k)$, then $Pb$ can be solved in polynomial time for any value of $k$, so there is no need to consider the parameter $k$ to refine its analysis beyond $P$.
* more generally, consider the case where $f(k)$ is locally decreasing on some intervals, but that there is a strictly increasing integer function $g()$ such that $f(g(k))$ is non decreasing: while being able to solve $Pb$ faster for some particular values of $k$ might be interesting in practice, in theory we are interested in solving it faster all the time (now knowing what future instances will look like), so we focus on the parts where $f()$
  is non decreasing and, "without loss of generality", just assume that $f()$ is non decreasing to avoid having to introduce the function $g()$.

> **Comments:**
> **username_0**: I will read it word by word tonight after showering. Thank you first for this detailed explain, this afternoon, I got some simple explain from another book which is called "Parameterized Algorithm", I will share it with you later.  I guess i am lacking of some knowledge on computational analysis, some terms are not familiar to me. And it makes it hard to understand the book "Parameterized Complexity Theory" on the first chapter.  Thanks!  
> **username_2**: You are making it way too complicated, and I’m sure this not what the authors meant. Simply, if $\mathbb A'$ decides $(Q',\kappa')$ in time (at most) $f'(k')\cdot p'(|x'|)$, it also decides it in time $f''(k')\cdot p'(|x'|)$, where $f''(k')=\max\{f'(n):n\le k'\}$ is nondecreasing. Thus, without loss of generality, we may assume $f'=f''$, i.e., that $f'$ is already nondecreasing.  

---

