On Friday March 28, 2014, Hubie Chen (Universidad del País Vasco / Euskal Herriko Unibertsitateko and Basque Foundation for Science / Ikerbasque) will give the following talk at the regular seminar of MPLA.

Title: One Hierarchy Spawns Another: The Complexity Classification of Conjunctive Queries

Abstract: We study the problem of conjunctive query evaluation over sets of queries; this problem is formulated here as the relational homomorphism problem over 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 introduce a notion which we call graph deconstruction, which is a variant of the well-known notion of tree decomposition. Using this notion, we give a novel, modular, and conceptually clean presentation of the theorem describing the tractable homomorphism problems in the framework under study (assuming bounded arity).

We then study a binary relation on graph classes that is naturally induced by the notion of graph deconstruction. We completely describe the hierarchy of graph classes that this binary relation yields, and discuss how this hierarchy of graph classes can be used to infer a complexity-theoretic hierarchy of homomorphism problems, which is extremely fine as it is exhaustive up to a computationally very weak notion of reduction (namely, a parameterized form of quantifier-free reduction).