Skip to Main content Skip to Navigation
Conference papers

When is the evaluation of conjunctive queries tractable ?

Abstract : The evaluation of conjunctive queries is hard both with respect to its combined complexity (NP-complete) and its pa-rameterized complexity (W[1]-complete). It becomes trac-table (PTIME for combined complexity, FPT for parame-terized complexity), when the underlying graphs of the con-junctive queries have bounded tree-width [2]. We show that, in some sense, this is optimal both with respect to combined and parameterized complexity: For every class C of graphs, the evaluation of all conjunctive queries whose underlying graph is in C is tractable if, and only if, C has bounded tree-width. A technical result of independent interest is that the colored grid homomorphism problem is NP-complete and, if param-eterized by the grid size, W[1]-complete.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Luc Segoufin Connect in order to contact the contributor
Submitted on : Thursday, January 17, 2019 - 1:59:26 PM
Last modification on : Friday, February 4, 2022 - 3:10:02 AM


Files produced by the author(s)


  • HAL Id : hal-01984895, version 1



Martin Grohe, Thomas Schwentick, Luc Segoufin. When is the evaluation of conjunctive queries tractable ?. STOC 2001 - Thirty-Third Annual ACM Symposium on Theory of Computing, Jul 2001, Heraklion, Greece. ⟨hal-01984895⟩



Record views


Files downloads