In the database context, the hypertree decomposition method is used for query optimization,
whereby conjunctive queries having a low degree of cyclicity can be recognized and …

Evaluating the relational join is one of the central algorithmic and most well-studied
problems in database systems. A staggering number of variants have been considered …

The chase algorithm is a fundamental tool for query evaluation and for testing query
containment under tuple-generating dependencies (TGDs) and equality-generating …

Several important decision problems on conjunctive queries (CQs) are NP-complete in
general but become tractable, and actually highly parallelizable, if restricted to acyclic or …

We define and study the Functional Aggregate Query (FAQ) problem, which encompasses
many frequently asked questions in constraint satisfaction, databases, matrix operations …

Graph searching encompasses a wide variety of combinatorial problems related to the
problem of capturing a fugitive residing in a graph using the minimum number of searchers …

We give a complexity theoretic classification of homomorphism problems for graphs and,
more generally, relational structures obtained by restricting the left hand side structure in a …

This paper surveys recent results related to the concept of hypertree decomposition and the
associated notion of hypertree width. A hypertree decomposition of a hypergraph (similar to …

Many important combinatorial problems can be modeled as constraint satisfaction problems.
Hence, identifying polynomial-time solvable classes of constraint satisfaction problems has …

Combinatorial games lead to several interesting, clean problems in algorithms and
complexity theory, many of which remain open. The purpose of this paper is to provide an …