Skip Navigation


Journal of Logic and Computation Advance Access originally published online on August 3, 2008
Journal of Logic and Computation 2009 19(1):89-122; doi:10.1093/logcom/exn029
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Chen, Y.
Right arrow Articles by Flum, J.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2008. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

This article appears in the following Journal of Logic and Computation issue: Special Issue: Logic and Computation in the Real World: CiE 2007 [View the issue table of contents]

Original Articles

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

Yijia Chen

BASICS, Department of Computer Science, Shanghai Jiaotong University, Shanghai 200030, China
E-mail: yijia.chen{at}cs.sjtu.edu.cn

Jörg Flum

Abteilung für Mathematische Logik, Universität Freiburg, Eckerstr. 1, 79104 Freiburg, Germany
E-mail: joerg.flum{at}math.uni-freiburg.de

Received 26 September 2007.

Recently it has been shown that the miniaturization mapping M faithfully translates bexponential parameterized complexity into (unbounded) parameterized complexity. We determine the pre-images under M 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: Parameterized complexity; exponential time complexity; miniaturization mapping



References

  1. Abrahamson KA, Downey RG, Fellows MR. Fixed-parameter tractability and completeness IV: on completeness for W[P] and PSPACE analogs. Annals of Pure and Applied Logic (1995) 73:235–276.[CrossRef][Web of Science]
  2. Chen J, Chor B, Fellows M, Huang X, Juedes D, Kanj I, Xia Ge. Tight lower bounds for certain parameterized NP-hard problems. In Proceedings of The 19th IEEE Annual Conference on Computational Complexity (CCC’04) (2004) 150–160.
  3. Chen Y, Grohe M. An isomorphism between subexponential and parameterized complexity theory. SIAM Journal on Computing (2007) 37:1228–1258.[CrossRef][Web of Science]
  4. Doner J. Tree acceptors and some of their applications. Journal of Computer and System Sciences (1970) 4:406–451.[CrossRef]
  5. Downey RG, Fellows MR. Parameterized Complexity. (1999) NewYork: Springer-Verlag.
  6. Flum J, Grohe M. Parameterized complexity and subexponential time. In: In the Complexity Column of the Bulletin of the European Association for Theoretical Computer Science (EATCS). (2004) 84, October.
  7. Flum J, Grohe M. Model-checking problems as a basis for parameterized intractability. Logical Methods in Computer Science (2005) 1:1–36.
  8. Flum J, Grohe M. Parameterized Complexity Theory. (2006) Berlin-Heidelberg: Springer-Verlag.
  9. Flum J, Grohe M, Weyer M. Bounded fixed-parameter tractability and log2n nondeterministic bits. Journal of Computer and System Sciences (2006) 72:34–71.[CrossRef][Web of Science]
  10. Frick M, Grohe M. The complexity of first-order and monadic second-order logic revisited. Annals of Pure and Applied Logic (2004) 130:3–31.[CrossRef][Web of Science]
  11. Khot S, Raman V. Parameterized complexity of finding subgraphs with hereditary properties. Theoretical Computer Science (2002) 289:997–1008.[CrossRef][Web of Science]
  12. Papadimitriou CH, Yannakakis M. On the complexity of database queries. Journal of Computer and System Sciences (1999) 58:407–427.[CrossRef][Web of Science]
  13. Thatcher JW, Wright JB. Generalised finite automata theory with an application to a decision problem of second-order logic. Mathematical Systems Theory (1968) 2:57–81.[CrossRef]

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Chen, Y.
Right arrow Articles by Flum, J.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?