We present new algorithms for exact multilinear k-monomial counting which is to compute the sum of coefficients of all degree-k multilinear monomials in a given polynomial P over a ring R described by an arithmetic circuit C. If the polynomial can be represented as a product of two polynomials with degree at most d < k, our algorithm can solve this problem in O~*(({under}n{down}(↓d))) time, where ({under}n{down}(↓d)) = ∑_(i=0)~d ({under}n{down}i). O~* omits a polynomial factor in n. For the general case, the proposed algorithm takes time O~*(({under}n{down}(↓k))). In both cases, our results are superior to previous approaches presented in [Koutis, I. and Williams, R.: Limits and applications of group algebras for parameterized problems. ICALP, pages 653-664 (2009)]. We also present a polynomial space algorithm with time bound O~*(2~k ({under}n{down}k)). By reducing the #k-path problem and the #m-set k-packing problem to the exact multilinear k-monomial counting problem, we give algorithms for these two problems that match the fastest known results presented in [2].
展开▼
