When is the evaluation of conjunctive queries tractable?

The evaluation of conjunctive queries is hard both with respect to its combined complexity (NP-complete) and its parameterized complexity (W[1]-complete). It becomes tractable (PTIME for combined complexity, FPT for parameterized complexity), when the underlying graphs of the conjunctive 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 parameterized by the grid size, W[1]-complete.

Authors

• Martin Grohe
• Thomas Schwentick
• Luc Segoufin

Keywords

No keywords are indexed for this paper.