10
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ I don't understand what you mean by an "FPT NP-complete language". There's no natural notion of a language by itself being FPT; the question is whether a language/parameter pair is FPT. $\endgroup$ – Huck Bennett Nov 19 '15 at 19:44
  • 4
    $\begingroup$ Note that a fixed-parameter reduction can just solve an FPT problem, and output a trivial Yes/No instance of the target problem. $\endgroup$ – Serge Gaspers Nov 24 '15 at 22:19
8
$\begingroup$

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.

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