Exact Parameterized Multilinear Monomial Counting via k-Layer Subset Convolution and k-Disjoint Sum

摘要

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~*((↓_d~n)) time, where (↓_d~n) = ∑_(i=o)~d (n/i). O~* omits a polynomial factor in n. For the general case, the proposed algorithm takes time O~*((↓_d~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(d n)). 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].