Efficient Computation of Representative Weight Functions with Applications to Parameterized Counting (Extended Version)

In this paper we prove an analogue of the classic Bollobás lemma for approximate counting. In fact, we match an analogous result of Fomin et al. [JACM 2016] for decision. This immediately yields, for a number of fundamental problems, parameterized approximate counting algorithms with the same running times as what is obtained for the decision variant using the representative family technique of Fomin et al. [JACM 2016]. For example, we devise an algorithm for approximately counting (a factor (1 ± ∊) approximation algorithm) k-paths in an n-vertex directed graph (#k-Path) running in time (n + m)). This improves over an earlier algorithm of Brand et al. [STOC 2018] that runs in time . Additionally, we obtain an approximate counting analogue of the efficient computation of representative families for product families of Fomin et al. [TALG 2017], again essentially matching the running time for decision. This results in an algorithm with running time for computing a (1 + ∊) approximation of the sum of the coefficients of the multilinear monomials in a degree-k homogeneous n-variate polynomial encoded by a monotone circuit (#Multilinear Monomial Detection). When restricted to monotone circuits (rather than polynomials of non-negative coefficients), this improves upon an earlier algorithm of Pratt [FOCS 2019] that runs in time .