Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping
- 3 August 2008
- journal article
- research article
- Published by Oxford University Press (OUP) in Journal of Logic and Computation
- Vol. 19 (1), 89-122
- https://doi.org/10.1093/logcom/exn029
Abstract
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.Keywords
This publication has 8 references indexed in Scilit:
- An Isomorphism Between Subexponential and Parameterized Complexity TheorySIAM Journal on Computing, 2007
- Bounded fixed-parameter tractability and nondeterministic bitsJournal of Computer and System Sciences, 2006
- The complexity of first-order and monadic second-order logic revisitedAnnals of Pure and Applied Logic, 2004
- Parameterized complexity of finding subgraphs with hereditary propertiesTheoretical Computer Science, 2002
- On the Complexity of Database QueriesJournal of Computer and System Sciences, 1999
- Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analoguesAnnals of Pure and Applied Logic, 1995
- Tree acceptors and some of their applicationsJournal of Computer and System Sciences, 1970
- Generalized finite automata theory with an application to a decision problem of second-order logicTheory of Computing Systems, 1968