Need more explaination on this 'generality'

Question

I am trying to understand how this proof works

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.

Answer 1

(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()$.