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

Moritz Müller, Hubie Chen

    Veröffentlichungen: Beitrag in BuchBeitrag in Konferenzband


    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 and completely describe the resulting hierarchy given by this relation. This binary 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 reductions. 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- Fraïssé-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.

    TitelProceedings of the Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic, CSL 2014 and the 29th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2014
    UntertitelVienna, Austria — July 14 - 18, 2014
    Herausgeber (Verlag)Association for Computing Machinery (ACM)
    ISBN (Print)9781450328869
    PublikationsstatusVeröffentlicht - 2014

    ÖFOS 2012

    • 102031 Theoretische Informatik
    • 101013 Mathematische Logik
    • 101011 Graphentheorie