On Polynomials Defined by Acyclic Conjunctive Queries and Weighted Counting Problems
Arnaud Durand, Stefan Mengel · arXiv (Cornell University) · 2011
This paper is a study of weighted counting problems associated to acyclic conjunctive queries ($\ACQ$) and the polynomials they define. We prove that summing the weights of solutions of quantifier-free $\ACQ$ queries can be done in polynomial time. We also show that minimalistic extensions of the problem (introducing one quantified variable, considering disjunction or conjunction of two $\ACQ$ instances) lead to intractable problems. However, we 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.