Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping
Y. Chen, J. Flum · Journal of Logic and Computation · 2008
Recently it has been shown that the miniaturization mapping ℳ faithfully translates bexponential parameterized complexity into (unbounded) parameterized complexity. We determine the pre-images under ℳ of various (classes of) problems. For many parameterized problems whose underlying classical problem is in NP we show that the pre-images coincide with natural reparameterizations that take into account the amount of non-determinism needed to solve them.