3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Jesus, they deliberately try to make it harder than it needs to be. $\endgroup$ – Pål GD Oct 29 '17 at 19:40
  • $\begingroup$ The "oracle" is just whatever algorithm solves problem $G$, and then the "reduction" uses that algorithm to solve different $y$s. $\endgroup$ – Pål GD Oct 29 '17 at 19:53
  • $\begingroup$ Absolutely, oracle reduction is nothing new and an entirely standard technique, sure. But, an FPT Turing reduction, is a specific kind of oracle reduction between parameterized problems. So we have to be a little more careful in ensuring that nothing wild is happening with the parameter of our instance when we feed some oracle a query. The last condition I am struggling with asserts this, but I'm not quite sure what this says. $\endgroup$ – j x Oct 29 '17 at 20:40
  • $\begingroup$ The last condition you mention ($l(y)$ being bounded by a computational function of $k(x)$) is there to ensure that if $G$ is FPT then $F$ is FPT (provided the reduction exists). If you look at the definition of FPT, you see that there must be an algorithm with complexity $g(k(x)) \cdot |x|^c$ for some $g,c$ for a problem to be FPT. $\endgroup$ – Pål GD Oct 29 '17 at 21:59
  • $\begingroup$ This hasn't really answered my question I'm afraid, I have already mentioned everything you have written (and I presume you mean computable function and not computational function). $\endgroup$ – j x Oct 30 '17 at 22:24
2
$\begingroup$

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))$.
$\endgroup$

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.