{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T07:10:15Z","timestamp":1791270615777,"version":"4.1.0"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2001,1]]},"abstract":"<jats:p>In this article, we study parameterized complexity theory from the perspective of logic, or more specifically, descriptive complexity theory.<\/jats:p>\n                  <jats:p>We propose to consider parameterized model-checking problems for various fragments of first-order logic as generic parameterized problems and show how this approach can be useful in studying both fixed-parameter tractability and intractability. For example, we establish the equivalence between the model-checking for existential first-order logic, the homomorphism problem for relational structures, and the substructure isomorphism problem. Our main tractability result shows that model-checking for first-order formulas is fixed-parameter tractable when restricted to a class of input structures with an excluded minor. On the intractability side, for every $t\\ge 0$ we prove an equivalence between model-checking for first-order formulas with t quantifier alternations and the parameterized halting problem for alternating Turing machines with t alternations. We discuss the close connection between this alternation hierarchy and Downey and Fellows' W-hierarchy.<\/jats:p>\n                  <jats:p>On a more abstract level, we consider two forms of definability, called Fagin definability and slicewise definability, that are appropriate for describing parameterized problems. We give a characterization of the class FPT of all fixed-parameter tractable problems in terms of slicewise definability in finite variable least fixed-point logic, which is reminiscent of the Immerman--Vardi theorem characterizing the class PTIME in terms of definability in least fixed-point logic.<\/jats:p>","DOI":"10.1137\/s0097539799360768","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"113-145","source":"Crossref","is-referenced-by-count":92,"title":["Fixed-Parameter Tractability, Definability, and Model-Checking"],"prefix":"10.1137","volume":"31","author":[{"given":"J\u00f6rg","family":"Flum","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","unstructured":"A. Aho, J. Hopcroft, and J. Ullman,\n                      The Design and Analysis of Computer Algorithms\n                      , Addison\u2010Wesley, Reading, MA, 1974."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1490"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/s001530050069"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"A. Chandra and P. Merlin,\n                      Optimal implementation of conjunctive queries in relational data bases\n                      , in Proceedings of the 9th ACM Symposium on Theory of Computing, Boulder, CO, 1977, pp. 77\u201390.","DOI":"10.1145\/800105.803397"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"C. Chekuri and A. Rajaraman,\n                      Conjunctive query containment revisited\n                      , in Proceedings of the 5th International Conference on Database Theory, P. Kolaitis and F. Afrati, eds., Lecture Notes in Comput. Sci. 1186, Springer\u2010Verlag, Berlin, 1997, pp. 56\u201370.","DOI":"10.1007\/3-540-62222-5_36"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"B. Courcelle,\n                      Graph rewriting: An algebraic and logic approach\n                      , in Handbook of Theoretical Computer Science, Vol. 2, J. van Leeuwen, ed., Elsevier, Amsterdam, 1990, pp. 194\u2013242.","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792228228"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"R. Downey and M. Fellows,\n                      Parameterized Complexity\n                      , Springer\u2010Verlag, New York, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"R. Downey, M. Fellows, and K. Regan,\n                      Descriptive complexity and the W\u2010hierarchy\n                      , in Proof Complexity and Feasible Arithmetics, P. Beame and S. Buss, eds., AMS\u2010DIMACS Proceedings Series 39, 1998, pp. 119\u2013134.","DOI":"10.1090\/dimacs\/039\/07"},{"key":"R12","unstructured":"R. Downey, M. Fellows, and U. Taylor,\n                      The parameterized complexity of relational database queries and an improved characterization of W\n                      [1], in Combinatorics, Complexity, and Logic, D. Bridges, C. Calude, J. Gibbons, S. Reeves, and I. Witten, eds., Springer\u2010 Verlag, 1996, pp. 194\u2013213."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"H.\u2010D. Ebbinghaus and J. Flum,\n                      Finite Model Theory\n                      , Springer\u2010Verlag, Berlin, 1995.","DOI":"10.1007\/3-540-28788-4"},{"key":"R14","unstructured":"R. Fagin,\n                      Generalized first\u2013order spectra and polynomial\u2013time recognizable sets\n                      , in Complexity of Computation, R. M. Karp, ed., Proc. Sympos. Appl. Math. 7, AMS, Providence, RI, 1974, pp. 43\u201373."},{"key":"R15","unstructured":"M. Fellows and U. Stege,\n                      An Improved Fixed\u2010Parameter\u2010Tractable Algorithm for Vertex Cover\n                      , Tech. Rep. 318, Department of Computer Science, ETH Zurich, Zurich, Switzerland, 1999."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"J. Flum, M. Frick, and M. Grohe,\n                      Query evaluation via tree\u2010decompositions\n                      , in Proceedings of the 8th International Conference on Database Theory, J. van den Bussche and V. Vianu, eds., Lecture Notes in Comput. Sci. 1973, Springer\u2010Verlag, Berlin, Heidelberg, New York, 2001, pp. 22\u201338.","DOI":"10.1007\/3-540-44503-X_2"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"M. Frickand M. Grohe,\n                      Deciding first\u2010order properties of locally tree\u2010decomposable graphs\n                      , in Proceedings of the 26th International Colloquiumon Automata, Languages and ProFIXED\u2010 gramming, J. Wiedermann, P. van Emde Boas, and M. Nielsen, eds., Lecture Notes in Comput. Sci. 1644, Springer\u2010Verlag, Berlin, 1999, pp. 331\u2013340.","DOI":"10.1007\/3-540-48523-6_30"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"G. Gottlob, N. Leone, and F. Scarcello,\n                      Hypertree decompositions and tractable queries\n                      , in Proceedings of the 18th ACM Symposium on Principles of Database Systems, Philadelphia, PA, 1999, pp. 21\u201332.","DOI":"10.1145\/303976.303979"},{"key":"R19","unstructured":"M. Grohe,\n                      Local tree\u2010width, excluded minors, and approximation algorithms\n                      , Combinatorica, to appear."},{"key":"R20","unstructured":"M. Grohe, T. Schwentick, and L. Segoufin,\n                      When is the evaluation of conjunctive queries tractable\n                      , in Proceedings of the 33rd ACM Symposium on Theory of Computing, Crete, Greece, to appear."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80029-8"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"N. Immerman,\n                      Descriptive Complexity\n                      , Springer\u2010Verlag, New York, 1999.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1031"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"P. Kolaitis and M. Vardi,\n                      Conjunctive\u2010query containment and constraint satisfaction\n                      , in Proceedings of the 17th ACM Symposium on Principles of Database Systems, Seattle, WA, 1998, pp. 205\u2013213.","DOI":"10.1145\/275487.275511"},{"key":"R25","unstructured":"P. G. Kolaitis and M. Y. Vardi,\n                      On the expressive power of variable\u2010confined logics\n                      , in Proceedings of the 11th IEEE Symposium on Logic in Computer Science, New Brunswick, NJ, 1996."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou and M. Yannakakis,\n                      On the complexity of database queries\n                      , in Proceedings of the 17th ACM Symposium on Principles of Database Systems, Tucson, AZ, 1997, pp. 12\u201319.","DOI":"10.1145\/263661.263664"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"J. Plehn and B. Voigt,\n                      Finding minimally weighted subgraphs\n                      , in Graph\u2010Theoretic Concepts in Computer Science, R. M\u00f6hring, ed., Lecture Notes in Comput. Sci. 484, Springer\u2010Verlag, Berlin, 1991, pp. 18\u201329.","DOI":"10.1007\/3-540-53832-1_28"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129500070079"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"M. Vardi,\n                      The complexity of relational query languages\n                      , in Proceedings of the 14th ACM Symposium on Theory of Computing, San Francisco, CA, 1982, pp. 137\u2013146.","DOI":"10.1145\/800070.802186"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"M. Vardi,\n                      On the complexity of bounded\u2010variable queries\n                      , in Proceedings of the 14th ACM Symposium on Principles of Database Systems, San Jose, CA, 1995, pp. 266\u2013276.","DOI":"10.1145\/212433.212474"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539799360768","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:20:20Z","timestamp":1787336420000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539799360768"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["10.1137\/S0097539799360768"],"URL":"https:\/\/doi.org\/10.1137\/s0097539799360768","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}