skip to content

The complexity of enumeration and counting for acyclic conjunctive queries

Tuesday 27th March 2012 - 14:00 to 15:00
INI Seminar Room 1
Enumerating all the solutions of a problem or counting the number of these solutions are two related algorithmic tasks. Complexity measures, however, are of a different nature. For enumeration problem, for example, one of the main notion is that of delay between generated solutions. A problem is considered as tractable if one can enumerate the solutions one by one without repetition with a "reasonable" delay (e.g. polynomial, linear or constant time) between two solutions.

In this talk, we will make a tour on the complexity of enumeration and (weighted) counting for acyclic conjunctive queries (ACQ), a well-known tractable fragment (for decision) of conjunctive queries.

We first show that there is a dichotomy for enumeration and, up to some reasonable complexity assumption, such queries are either enumerable with a linear or with a "constant" delay. Hence, in all cases, enumeration is tractable.

For weighted counting, the situation is more complex. The unweighted quantifier free version of this problem is known to be tractable (for combined complexity), but it is also known that introducing even a single quantified variable makes it #P-hard. By introducing some polynomial representation of queries, we first show that weighted counting for quantifier-free ACQ is still tractable and that even minimalistic extensions of the problem lead to hard cases. We then introduce a new parameter for quantified queries that permits to isolate large island of tractability. We show that, up to a standard assumption from parameterized complexity, this parameter fully characterizes tractable subclasses for counting weighted solutions of ACQ queries. This completely determine the tractability frontier for weighted counting in this case.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons