Abstract
We introduce a general notion of miniaturization of a problem that comprises the different miniaturizations of concrete problems considered so far. We develop parts of the basic theory of miniaturizations in this general framework. Using the appropriate logical formalism, we show that the miniaturization of a definable problem in W[t] lies in W[t], too. In particular, the miniaturization of the dominating set problem is in W[2].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cai, L., Juedes, D.: Subexponential parameterized algorithms collapse the Whierarchy. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, p. 273. Springer, Heidelberg (2001)
Chen, J., Huang, X., Kanj, I., Xia, G.: Linear FPT Reductions and Computational Lower Bounds. In: Proceedings of STOC 2004 (2004)
Downey, R.: Parameterized complexity for the sceptic. In: Proceedings of the 18th IEEE Conference on Computational Complexity, pp. 147–168 (2003)
Downey, R., Estivill, V., Fellows, M., Prieto, E., Rosamond, F.: Cutting up is hard to do: the parameterized complexity of k-cut and related problems. In: Proceedings of CATS 2003. ENTCS, vol. 78(0) (2003)
Downey, R.G., Fellows, M.R., Regan, K.: Descriptive complexity and the Whierarchy. In: Beame, P., Buss, S. (eds.) Proof Complexity and Feasible Arithmetic. AMS-DIMACS Volume Series, vol. 39, pp. 119–134. AMS, Providence (1998)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Fellows, M.: New directions and new challenges in algorithm design and complexity, parameterized. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 505–519. Springer, Heidelberg (2003)
Flum, J., Grohe, M.: Fixed-parameter tractability, definability, and model checking. SIAM Journal on Computing 31(1), 113–145 (2001)
Flum, J., Grohe, M., Weyer, M.: Bounded fixed-parameter tractability and log2n nondeterministic bits. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 555–567. Springer, Heidelberg (2004)
Impagliazzo, R., Paturi, R.: Complexity of k-SAT. JCSS 62(2), 367–375 (2001)
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? JCSS 63(4), 512–530 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, Y., Flum, J. (2004). On Miniaturized Problems in Parameterized Complexity Theory. In: Downey, R., Fellows, M., Dehne, F. (eds) Parameterized and Exact Computation. IWPEC 2004. Lecture Notes in Computer Science, vol 3162. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28639-4_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-28639-4_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23071-7
Online ISBN: 978-3-540-28639-4
eBook Packages: Springer Book Archive