One hierarchy spawns another: graph deconstructions and the complexity classification of conjunctive queries

DOI10.1145/2603088.2603107MaRDI QIDQ4635616zbMATH OpenOpenAlexFDO

Authors Hubie Chen, Moritz Müller

Publication date 23 April 2018

Published in Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.1353

zbMATH Keywords

conjunctive queriesgraph decompositionshomomorphismsparameterized complexity

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75) Database theory (68P15) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Abstract: We study the problem of conjunctive query evaluation relative to a class of queries; this problem is formulated here as the relational homomorphism problem relative to a class of structures A, wherein each instance must be a pair of structures such that the first structure is an element of A. We present a comprehensive complexity classification of these problems, which strongly links graph-theoretic properties of A to the complexity of the corresponding homomorphism problem. In particular, we define a binary relation on graph classes, which is a preorder, and completely describe the resulting hierarchy given by this relation. This relation is defined in terms of a notion which we call graph deconstruction and which is a variant of the well-known notion of tree decomposition. We then use this hierarchy of graph classes to infer a complexity hierarchy of homomorphism problems which is comprehensive up to a computationally very weak notion of reduction, namely, a parameterized version of quantifier-free first-order reduction. In doing so, we obtain a significantly refined complexity classification of homomorphism problems, as well as a unifying, modular, and conceptually clean treatment of existing complexity classifications. We then present and develop the theory of Ehrenfeucht-Fraisse-style pebble games which solve the homomorphism problems where the cores of the structures in A have bounded tree depth. Finally, we use our framework to classify the complexity of model checking existential sentences having bounded quantifier rank.

Recommendations

• One hierarchy spawns another, graph deconstructions and the complexity classification of conjunctive queries
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• When is the evaluation of conjunctive queries tractable?
• The fine classification of conjunctive queries and parameterized logarithmic space
• scientific article; zbMATH DE number 7297854

Cited in

(4)

• How many variables are needed to express an existential positive query?
• One hierarchy spawns another, graph deconstructions and the complexity classification of conjunctive queries
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
• On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism

This page was built for publication: One hierarchy spawns another: graph deconstructions and the complexity classification of conjunctive queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635616)