direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Ehemalige Mitarbeiter

Dr. Stefan Mengel


CRIL-CNRS/Université d'Artois
Faculté des Sciences Jean Perrin
rue Jean Souvraz, S.P. 18
F-62307 LENS Cedex
Persönliche Homepage

Publikationen in der Arbeitsgruppe

The Complexity of Weighted Counting for Acyclic Conjunctive Queries
Citation key DM-The-Complexity-Of-Weighted-Counting-For-Acyclic-Conjunctive-Queries
Author Arnaud Durand and Stefan Mengel
Pages 277-296
Year 2014
DOI 10.1016/j.jcss.2013.08.001
Journal Journal of Computer and System Sciences
Volume 80
Number 1
Abstract This paper is a study of weighted counting of the solutions of acyclic conjunctive queries (ACQ). 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. 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. Thus we completely determine the tractability frontier for weighted counting for ACQ.
Link to publication Link to original publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.