Parameterized counting matching and packing: A family of hard problems that admit FPTRAS

In the field of parameterized counting complexity, the problems that are #W[1]-hard and admit fixed-parameter tractable randomized approximation scheme (FPTRAS) have attracted much attention in recent years. In this paper, we focus on the problems on parameterized counting matching and packing. These problems include counting set packing, counting matching, and counting subgraph packing (including both vertex-disjoint and edge-disjoint versions). We study the parameterized complexity on these problems. On the basis of some results for counting graph matchings, we show that a series of problems are #W[1]-hard. Furthermore, by extending the previous algorithm for counting 3-d matching, we obtain FPTRAS for each considered problem, respectively. Our results indicate that the problems on parameterized counting matching and packing form a large family of problems that are #W[1]-hard and admit FPTRAS.