Subexponential Time and Fixed-Parameter Tractability: Exploiting the Miniaturization Mapping

Abstract Recently a mapping, the so-called miniaturization mapping, has been introduced and it has been shown that faithfully translates subexponential parameterized complexity into (unbounded) parameterized complexity [2]. We determine the preimages under of various (classes of) problems and show that they coincide with natural reparameterizations which take into account the amount of nondeterminism needed to solve them.

Authors

• Yijia Chen 0001
• Jörg Flum

Keywords

No keywords are indexed for this paper.