Skip to main content
Springer Nature Link
Log in

Descriptive and Parameterized Complexity

  • Conference paper
  • First Online:
Computer Science Logic (CSL 1999)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1683))

Included in the following conference series:

Abstract

Descriptive Complexity Theory studies the complexity of problems of the following type: Given a finite structure A and a sentence φ of some logic L, decide if A satisfies φ? In this survey we discuss the parameterized complexity of such problems. Basically, this means that we ask under which circumstances we have an algorithm solving the problem in time f(|φ|)‖A‖c, where ƒ is a computable function and c > 0 a constant. We argue that the parameterized perspective is most appropriate for analyzing typical practical problems of the above form, which appear for example in database theory, automated verification, and artificial intelligence.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
€34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 42.79
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 53.49
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

') var buybox = document.querySelector("[data-id=id_"+ timestamp +"]").parentNode var buyingOptions = buybox.querySelectorAll(".buying-option") ;[].slice.call(buyingOptions).forEach(initCollapsibles) var buyboxMaxSingleColumnWidth = 480 function initCollapsibles(subscription, index) { var toggle = subscription.querySelector(".buying-option-price") subscription.classList.remove("expanded") var form = subscription.querySelector(".buying-option-form") var priceInfo = subscription.querySelector(".price-info") var buyingOption = toggle.parentElement if (toggle && form && priceInfo) { toggle.setAttribute("role", "button") toggle.setAttribute("tabindex", "0") toggle.addEventListener("click", function (event) { var expandedBuyingOptions = buybox.querySelectorAll(".buying-option.expanded") var buyboxWidth = buybox.offsetWidth ;[].slice.call(expandedBuyingOptions).forEach(function(option) { if (buyboxWidth buyboxMaxSingleColumnWidth) { toggle.click() } else { if (index === 0) { toggle.click() } else { toggle.setAttribute("aria-expanded", "false") form.hidden = "hidden" priceInfo.hidden = "hidden" } } }) } initialStateOpen() if (window.buyboxInitialised) return window.buyboxInitialised = true initKeyControls() })()

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. S. Arnborg, D. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic Discrete Methods, 8:277–284,1987.

    Article  MathSciNet  Google Scholar 

  2. S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12:308–340, 1991.

    Article  MathSciNet  Google Scholar 

  3. N. Alon, R. Yuster, and U. Zwick. Color-coding. Journal of the ACM,42:844–856, 1995.

    Article  MathSciNet  Google Scholar 

  4. H.L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25:1305–1317, 1996.

    Article  MathSciNet  Google Scholar 

  5. H.L. Bodlaender. Treewidth: Algorithmic techniques and results. In I. Privara and P. Ruzicka, editors, Proceedings 22nd International Symposium on Mathematical Foundations of Computer Science, MFCS’97, volume 1295 of Lecture Notes in Computer Science, pages 29–36. Springer-Verlag, 1997.

    Google Scholar 

  6. A.K. Chandra and P.M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the 9th ACM Symposium on Theory of Computing, pages 77–90, 1977.

    Google Scholar 

  7. B. Courcelle, J.A. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs of bounded clique width. In Graph Theoretic Concepts in Computer Science, WG’98, volume 1517 of Lecture Notes in Computer Science, pages 1–16. Springer-Verlag, 1998.

    Chapter  Google Scholar 

  8. B. Courcelle. Graph rewriting: An algebraic and logic approach. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume 2, pages 194–242. Elsevier Science Publishers, 1990.

    Google Scholar 

  9. R.G. Downey and M.R. Fellows. Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science, 141:109–131, 1995.

    Article  MathSciNet  Google Scholar 

  10. R.G. Downey and M.R. Fellows. Parametrized Complexity. Springer-Verlag, 1999.

    Google Scholar 

  11. R.G. Downey, M.R. Fellows, and K. Regan. Descriptive complexity and the W-hierarchy. In P. Beame and S. Buss, editors, Proof Complexity and Feasible Arithmetic, volume 39 of AMS-DIMACS Volume Series, pages 119–134. AMS, 1998.

    Google Scholar 

  12. R.G. Downey, M.R. Fellows, and U. Taylor. The parametrized complexity of relational database queries and an improved characterization of W[1]. In Bridges, Calude, Gibbons, Reeves, and Witten, editors, Combinatorics, Complexity, and Logic Proceedings-of DMTCS’ 96, pages 194–213. Springer-Verlag, 1996.

    Google Scholar 

  13. R. Diestel. Graph Theory. Springer-Verlag, 1997.

    Google Scholar 

  14. J. Flum and M. Grohe. Fixed-parameter tractability and logic. In preparation.

    Google Scholar 

  15. M. Frick and M. Grohe. Deciding first-order properties of locally tree-decomposable graphs. In J. Wiedermann, P. van Emde Boas, M. Nielsen. editors, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, volume 1644 of Lecture Notes in Computer Science, pages 331–340. Springer-Verlag, 1999.

    Chapter  Google Scholar 

  16. T. Feder and M.Y. Vardi. Monotone monadic SNP and constraint satisfaction. In Proceedings of the 25th ACM Symposium on Theory of Computing, pages 612–622, 1993.

    Google Scholar 

  17. H. Gaifman. On local and non-local properties. In Proceedings of the Herbrand Symposium, Logic Colloquium’ 81. North Holland, 1982.

    Google Scholar 

  18. M.R. Garey, D.S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1:237–267, 1976.

    Article  MathSciNet  Google Scholar 

  19. M. Grohe and K. Luosto. Private communication.

    Google Scholar 

  20. R. Halin. S-Functions for graphs. Journal of Geometry, 8:171–186, 1976.

    Article  MathSciNet  Google Scholar 

  21. W. Hanf. Model-theoretic methods in the study of elementary logic. In J. Addison, L. Henkin, and A. Tarski, editors, The Theory of Models, pages 132–145. North Holland, 1965. au][Imm86] N. Immerman. Relational queries computable in polynomial time. Information and Control, 68:86–104, 1986.

    Google Scholar 

  22. R.M. Karp. Reducibilities among combinatorial problems. In R.E. Miller and J.W. Thatcher, editors, Complexity of Computer Computations, pages 85–103. Plenum Press, New York, 1972.

    Chapter  Google Scholar 

  23. Ph.G. Kolaitis and M.Y. Vardi. Conjunctive-query containment and constraint satisfaction. In Proceedings of the 17th ACM Symposium on Principles of Database Systems, pages 205–213, 1998.

    Google Scholar 

  24. B. Mohar. Embedding graphs in an arbitrary surface in linear time. In Proceedings of the 28th ACM Symposium on Theory of Computing, pages 392–397, 1996.

    Google Scholar 

  25. J. Plehn and B. Voigt. Finiding minimally weighted subgraphs. In R. Möhring, editor, Graph-Theoretic Concepts in Computer Science, WG’ 90, volume 484 of Lecture Notes in Computer Science, pages 18–29. Springer-Verlag, 1990.

    Chapter  Google Scholar 

  26. C.H. Papadimitriou and M. Yannakakis. On the complexity of database queries. In Proceedings of the 16th ACM Symposium on Principles of Database Systems, pages 12–19, 1997.

    Google Scholar 

  27. N. Robertson and P.D. Seymour. Graph minors II. Algorithmic aspects of tree-width. Journal of Algorithms, 7:309–322, 1986.

    Article  MathSciNet  Google Scholar 

  28. N. Robertson and P.D. Seymour. Graph minors V. Excluding a planar graph. Journal of Combinatorial Theory, Series B, 41:92–114, 1986.

    Article  MathSciNet  Google Scholar 

  29. N. Robertson and P.D. Seymour. Graph minors XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B, 63:65–110, 1995.

    Article  MathSciNet  Google Scholar 

  30. N. Robertson and P.D. Seymour. Graph minors XVI. Excluding a non-planar graph. Journal of Combinatorial Theory, Series B. To appear.

    Google Scholar 

  31. D. Seese. Linear time computable problems and first-order descriptions. Mathematical Structures in Computer Science, 6:505–526, 1996.

    Article  MathSciNet  Google Scholar 

  32. L.J. Stockmeyer and A.R. Meyer. Word problems requiring exponential time. In Proceedings of the 5th ACM Symposium on Theory of Computing, pages 1–9, 1973.

    Google Scholar 

  33. J.P. Schmidt and A. Siegel. The spatial complexity of oblivious k-probe hash functions. SIAM Journal on Computing, 19:775–786, 1990.

    Article  MathSciNet  Google Scholar 

  34. M. Y. Vardi. The complexity of relational query languages. In Proceedings of the 14th ACM Symposium on Theory of Computing, pages 137–146, 1982.

    Google Scholar 

  35. M. Y. Vardi. On the complexity of bounded-variable queries. In Proceedings of the 14th ACM Symposium on Principles of Database Systems, pages 266–276, 1995.

    Google Scholar 

  36. M. Yannakakis. Perspectives on database theory. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pages 224–246, 1995.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Mathematische Logik, Eckerstr.1, 79104, Freiburg, Germany

    Martin Grohe

Authors
  1. Martin Grohe
    View author publications

    Search author on:PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Mathematisches Institut, Universität Freiburg, Eckerstr. 1, D-79104, Freiburg, Germany

    Jörg Flum

  2. Dpto. de Sistemas Informáticos y Programación Edificio Fac. Matemáticas, Universidad Complutense de Madrid, Av. Complutense s/n, E-28040, Madrid, Spain

    Mario Rodriguez-Artalejo

Rights and permissions

Reprints and permissions

Copyright information

© 1999 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Grohe, M. (1999). Descriptive and Parameterized Complexity. In: Flum, J., Rodriguez-Artalejo, M. (eds) Computer Science Logic. CSL 1999. Lecture Notes in Computer Science, vol 1683. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48168-0_3

Download citation

  • DOI: https://doi.org/10.1007/3-540-48168-0_3

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-66536-6

  • Online ISBN: 978-3-540-48168-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics