Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic

Question

Berman–Hartmanis conjecture: all NP-complete languages look alike, in the sense that they can be related to each other by polynomial time isomorphisms[1].

I am interested in a more fine-grained version of the "polynomial time", that is, if we use parameterized reductions.

A parameterized problem is a subset of $Σ^∗ × Z \geq 0$, where $Σ$ is a finite alphabet and $Z\geq 0$ is the set of nonnegative numbers. An instance of a parameterized problem is therefore a pair $(I, k)$, where $k$ is the parameter.

A parameterized problem $π_1$ is fixed-parameter reducible to a parameterized problem $π_2$ if there exist functions $f$, $g$ : $Z≥0 → Z≥0$, $ Φ : Σ∗ × Z≥0 → Σ^∗$ and a polynomial $p(·)$ such that for any instance $(I, k)$ of $π_1$, $(Φ(I, k), g(k))$ is an instance of $π_2$ computable in time $f(k) · p(|I|)$ and $(I, k) ∈ π_1$ if and only if $(Φ(I, k), g(k)) ∈ π_2$. Two parameterized problems are fixed-parameter equivalent if they are fixed-parameter reducible to each other.

Some NP-complete problems are FPT, for example, the decision version of vertex cover problem is NP-Complete, it has a $O(1.2738^k + kn)$ algorithm[2]. Finding better fixed-parameter reductions of a FPT problem which is NP-Complete can lead to a better algorithm, for example, by invoking a reduction to an "above guarantee version" of the Multiway Cut problem can lead to an algorithm in time $O^*(4^k)$ for AGVC(Above Guarantee Vertex Cover) problem[3], which is better than the original $O^*(15^k)$ algorithm [4].

$\textbf{My Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic.}$

Is that conjecture true?

[1] Berman, L.; Hartmanis, J. (1977), "On isomorphisms and density of NP and other complete sets", SIAM Journal on Computing 6 (2): 305–322.

[2] J. Chen, I. A. Kanj, and G. Xia, Improved upper bounds for vertex cover, Theor.Comput. Sci., 411 (2010), pp. 3736-3756.

[3] M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk, On multiway cut parameterized above lower bounds, in IPEC, 2011.

[4] M. Mahajan and V. Raman, Parameterizing above guaranteed values: Maxsat and maxcut, J. Algorithms, 31 (1999), pp. 335-354.

Answer 1

Serge Gaspers already mentioned why your conjecture is trivially true.
However, one can in fact get polynomial-time fixed-parameter isomorphisms,
which I now realize isn't that much less trivial, since it applies to every
ordered pair of non-trivial FPT problems with a reduction in the ordinary sense.

Let $c$ be an integer that's greater than the degree of the FPT algorithm for $\pi_1$,
and let $Y$ and $N$ be a yes and no instance respectively of $\pi_2$.
The following will be a polynomial-time fixed-parameter reduction from $\pi_1$ to $\pi_2$:

Try the FPT algorithm on $\pi_1$ for up to $n^{\hspace{.02 in}c}$ steps.
If that gives an answer, then output $Y$ or $N$ as indicated by that answer.
Otherwise, output the result of applying an ordinary polynomial-time reduction from $\pi_1$ to $\pi_2$.


Correctness and polynomial runtime are obvious. $\:$ Since $c$ is greater than the degree of the FPT algorithm for $\pi_1$, it's the case that for each fixed $k$, there are only finitely many input lengths $n$ for which the FPT algorithm's maximum runtime is not less than $n^{\hspace{.02 in}c}$. $\:$ Thus, for each fixed $k$, the above reduction has only finitely many outputs. $\:$ Therefore it satisfies your fixed-parameter condition.