Martin Grohe
ABSTRACT
This paper gives a short introduction into parameterized complexity theory, aimed towards database theorists interested in this area. The main results presented here classify the evaluation of first-order queries and conjunctive queries as hard parameterized problems.
- 1.S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12:308-340, 1991.]] Google Scholar
Digital Library
- 2.L. Cai, J. Chen, R. Downey, and M. Fellows. Advice classes of parameterized tractability. Annals of pure and applied logic, 84:119-138, 1997.]]Google Scholar
- 3.A. Chandra and P. 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 ScholarDigital Library
- 4.C. Chekuri and A. Rajaraman. Conjunctive query containment revisited. In P. Kolaitis and F. Afrati, editors, Proceedings of the 5th International Conference on Database Theory, volume 1186 of Lecture Notes in Computer Science, pages 56-70. Springer-Verlag, 1997.]] Google ScholarDigital Library
- 5.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 ScholarDigital Library
- 6.B. Courcelle, J. 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.]] Google ScholarDigital Library
- 7.B. Courcelle and M. Mosbah. Monadic second-order evaluations on tree-decomposable graphs. Theoretical Computer Science, 103:49-82, 1993.]] Google ScholarDigital Library
- 8.R. Downey and M. Fellows. Fixed-parameter tractability and completeness I: Basic results. SIAM Journal on Computing, 24:873-921, 1995.]] Google ScholarDigital Library
- 9.R. Downey and M. Fellows. Fixed-parameter tractability and completeness II: On completeness for W{1}. Theoretical Computer Science, 141:109-131, 1995.]] Google ScholarDigital Library
- 10.R. Downey and M. Fellows. Parameterized Complexity. Springer-Verlag, 1999.]]Google ScholarCross Ref
- 11.R. Downey, M. Fellows, and K. Regan. Descriptive complexity and the W-hierarchy. InP. 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. Downey, M. Fellows, and K. Regan. Parameterized circuit complexity and the W-hierarchy. Theoretical Computer Science, 191:97-115, 1998.]] Google ScholarDigital Library
- 13.R. Downey, M. Fellows, and U. Taylor. The parameterized complexity ofrelational 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
- 14.M. Fellows and M. Langston. Nonconstructive tools for proving polynomial-time decidability. Journal of the ACM, 35, 1988.]] Google ScholarDigital Library
- 15.J. Flum, M. Frick, and M. Grohe. Query evaluation via tree-decompositions. In J. van den Bussche and V. Vianu, editors, Proceedings of the 8th International Conference on Database Theory, volume 1973 of Lecture Notes in Computer Science, pages 22-38. Springer Verlag, 2001. Full version currently available at http://www.math.uic.edu/~grohe/pub.html.]] Google ScholarDigital Library
- 16.J. Flum and M. Grohe. Fixed-parameter tractability, definability, and model checking. SIAM Journal on Computing. To appear.]] Google ScholarDigital Library
- 17.M. Frick and M. Grohe. Deciding first-order properties of locally tree-decomposable graphs. In J. Wiedermann, P. van Emde Boas, and 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.]] Google ScholarDigital Library
- 18.G. Gottlob, E. Gr.adel, and H. Veith. Datalog lite: A deductive query language with linear time model checking. ACM Transaction on Computational Logic. To appear.]] Google ScholarDigital Library
- 19.G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. In Proceedings of the 18th ACM Symposium on Principles of Database Systems, pages 21-32, 1999.]] Google ScholarDigital Library
- 20.G. Gottlob, N. Leone, and F. Scarcello. Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width. These proceedings.]] Google ScholarDigital Library
- 21.M. Grohe. Descriptive and parameterized complexity. In J. Flum and M. Rodriguez-Artalejo, editors, Computer Science Logic, 13th International Workshop CSL'99, volume 1683 of Lecture Notes in Computer Science, pages 14-31. Springer-Verlag, 1999.]] Google ScholarDigital Library
- 22.M. Grohe. Generalized model-checking problems for first-order logic. In H. Reichel and A. Ferreira, editors, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, volume 2010 of Lecture Notes in Computer Science, pages 12-26. Springer- Verlag, 2001.]] Google ScholarDigital Library
- 23.M. Grohe, T. Schwentick, and L. Segoufin. When is the evaluation of conjunctive queries tractable. In Proceedings of the 33rd ACM Symposium on Theory of Computing, 2001. To appear.]] Google ScholarDigital Library
- 24.N. Immerman. Descriptive Complexity. Springer-Verlag, 1999.]]Google Scholar
- 25.P. Kolaitis and M. Vardi. Conjunctive-query containment and constraint satisfaction. In Proceedings of the 17th ACM Symposium on Principles of Database Systems, pages 205-213, 1998.]] Google ScholarDigital Library
- 26.C. Papadimitriou and M. Yannakakis. On the complexity of database queries. In Proceedings of the 17th ACM Symposium on Principles of Database Systems, pages 12-19, 1997.]] Google ScholarDigital Library
- 27.D. Seese. Linear time computable problems and firstorder descriptions. Mathematical Structures in Computer Science, 6:505-526, 1996.]]Google ScholarCross Ref
- 28.L. Stockmeyer. The Complexity of Decision Problems in Automata Theory. PhD thesis, Department of Electrical Engineering, MIT, 1974.]]Google Scholar
- 29.M. Vardi. The complexity of relational query languages. In Proceedings of the 14th ACM Symposium on Theory of Computing, pages 137-146, 1982.]] Google ScholarDigital Library
- 30.M. Yannakakis. Algorithms for acyclic database schemes. In 7th International Conference on Very Large Data Bases, pages 82-94, 1981.]]Google ScholarDigital Library
- 31.M. Yannakakis. Perspectives on database theory. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pages 224-246, 1995.]] Google ScholarDigital Library
Index Terms
- The parameterized complexity of database queries
Recommendations
Parameterized complexity dichotomy for Steiner Multicut
We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = { T 1 , ź , T t } , T i ź V ( G ) , of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that ...
On parameterized exponential time complexity
In this paper we study the notion of parameterized exponential time complexity. We show that a parameterized problem can be solved in parameterized 2^o^(^f^(^k^)^)p(n) time if and only if it is solvable in time O(2^@d^f^(^k^)q(n)) for any constant @d>0, ...
The fine classification of conjunctive queries and parameterized logarithmic space complexity
PODS '13: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systemsWe perform a fundamental investigation of the complexity of conjunctive query evaluation from the perspective of parameterized complexity. We classify sets of boolean conjunctive queries according to the complexity of this problem. Previous work showed ...
Comments