Why are Oracle call instances bounded in the definition of FPT Turing reductions?

Question

Let's take the following definition of a FPT Turing reduction from Flum & Grohe's book.

Let $F$ and $G$ be parameterised problems. For any instance $x$ of $F$, write $k(x)$ for the parameter of $F$ and $|x|$ for the size of $x$. For any instance $y$ of $G$, write $l(y)$ for the parameter of $y$. An FPT Turing reduction from $F$ to $G$ is an algorithm with an oracle for $G$ that, for some computable functions $f, g : \mathbb{N} → \mathbb{N}$ and for some constant $c \in \mathbb{N}$, solves any instance $x$ of $F$ in time at most $f (k(x)) · |x|^c$ in such a way that for all oracle queries the instances $y$ of $G$ satisfy $l(y) ≤ g(k(x))$.

If we go through the definition in high-level terms I understand:

• We have an algorithm for $F$ that is allowed to call an oracle for the problem $G$ (this is done in constant time).
• The Algorithm must run in a time that is a computable function of the size of the parameter of our instance of $F$ multiplied by a polynomial function of the size of the instance of $F$.

I understand things thus far. However the final restriction that instances of the problem $y$ for which we make an oracle query must satisfy $l(y) ≤ g(k(x))$ for a computable function $g$ I do not understand. What does this say in high-level terms and why is it important? Thanks.

Answer 1

As Pål GD mentions, the requirement that $l(y)\leq g(k(x))$ is necessary to obtain reductions with the proper result. In particular, the property 'If $X$ is FPT, and there is an FPT-reduction from $Y$ to $X$ then $Y$ is FPT'.

An example to see why this requirement is necessary is to consider reductions between $k$-Clique and $k$-Vertex cover. Recall that we can construct polynomial time reductions both ways between Clique and Vertex cover (without the parameters), using the fact that if $X\subseteq V$ is a maximum clique in the graph $G$, then $V\setminus X$ is a minimum vertex cover in the complement of $G$.

However, this doesn't give a FPT reduction from $k$-clique to vertex cover: If we try to solve $k$-clique by finding a vertex cover in the complement of $G$, we need to find one of size $k'=|V|-k$. As $k$-vertex cover is FPT, applying the reduction and solving $k$-vertex cover can be done in $O(f(k')\cdot|G|^{O(1)})= O(f(|V|-k)\cdot|G^{O(1)}|)$. So, we don't get an FPT algorithm for $k$-clique from this 'reduction', as the 'non-polynomial' part of the running time depends on $|V|$! In fact, we shouldn't expect $k$-clique to have an FPT reduction to $k$-vertex cover, as $k$-vertex cover is FPT, but $k$-clique is $W[1]$-hard.

---

Additionally, I agree with Pål GD that the definition of parameterized Turing reductions you give is a bit difficult to read. I've looked at Flum & Grohe's book and their presentation of this definition is in fact a lot clearer than than one you provide (from a different book/edition?):

Definition 2.8. Let $(Q,\kappa)$ and $(Q' ,\kappa' )$ be parameterized problems over the alphabets $Σ$ and $Σ'$, respectively. An fpt Turing reduction from $(Q,\kappa)$ to $(Q' ,\kappa' )$ is an algorithm $\mathbb{A}$ with an oracle to $Q'$ such that:

1. $\mathbb{A}$ decides $(Q,\kappa)$.
2. $\mathbb{A}$ is an fpt-algorithm, that is, there is a computable function $f : \mathbb{N} \rightarrow \mathbb{N}$ and a polynomial $p(X)$ such that the running time of $\mathbb{A}$ on input $x \in \Sigma^*$ is bounded by $f(\kappa(x))\cdot p(|x|)$.
3. There is a computable function $g : \mathbb{N} \rightarrow \mathbb{N}$ such that for all oracle queries “$y \in Q'$?” posed by $\mathbb{A}$ on input $x$ we have $κ'(y) \leq g(κ(x))$.