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.