Computer Science – Computational Complexity
Scientific paper
2011-10-19
Computer Science
Computational Complexity
28 pages, 1 figure
Scientific paper
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 $\sP$-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$.
Durand Arnaud
Mengel Stefan
No associations
LandOfFree
The Complexity of Weighted Counting for Acyclic Conjunctive Queries does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Complexity of Weighted Counting for Acyclic Conjunctive Queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Weighted Counting for Acyclic Conjunctive Queries will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-597144