Approximation algorithms for some parameterized counting problems

We give a randomized fixed parameter tractable algorithm to approximately count the number of copies of a k-vertex graph with bounded treewidth in an n vertex graph. As a consequence, we get randomized algorithms with running time k(O(k))n(O(1)), approximation ratio 1/k(O(k)), and error probability 2(-nO(1)) for (a) approximately counting the number of matchings of size k in an n vertex graph and (b) approximately counting the number of paths of length k in an n vertex graph. Our algorithm is based on the Karp-Luby approximate counting technique [8] applied to fixed parameter tractable problems, and the color-coding technique of Alon, Yuster and Zwick [1]. We also show some W-hardness results for parameterized exact counting problems.