Skip to Main content Skip to Navigation
Conference papers

When is the evaluation of conjunctive queries tractable ?

Martin Grohe 1 Thomas Schwentick 2 Luc Segoufin 3
3 VERSO - Databases
Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8629
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

https://hal.inria.fr/hal-01984895
Contributor : Luc Segoufin <>
Submitted on : Thursday, January 17, 2019 - 1:59:26 PM
Last modification on : Thursday, August 1, 2019 - 2:12:40 PM

File

CQ-PTIME.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01984895, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

54

Files downloads

469