Affordable Access

Publisher Website

The complexity of weighted counting for acyclic conjunctive queries

Authors
Journal
Journal of Computer and System Sciences
0022-0000
Publisher
Elsevier
Volume
80
Issue
1
Identifiers
DOI: 10.1016/j.jcss.2013.08.001
Keywords
  • Conjunctive Queries
  • Counting Complexity

Abstract

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 a 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 for ACQs. Thus we completely determine the tractability frontier for weighted counting for ACQ.

There are no comments yet on this publication. Be the first to share your thoughts.