text: It is shown that one can count @math -edge paths in an @math -vertex graph and @math -set @math -packings on an @math -element universe, respectively, in time @math and @math , up to a factor polynomial in @math , @math , and @math ; in polynomial space, the bounds hold if multiplied by @math or @math , respectively. These are implications of a more general result: given two set families on an @math -element universe, one can count the disjoint pairs of sets in the Cartesian product of the two families with @math basic operations, where @math is the number of members in the two families and their subsets.
  @cite_5: 
  @cite_3: We present a fast algorithm for the subset convolution problem:given functions f and g defined on the lattice of subsets of ann-element set n, compute their subset convolution f*g, defined for S⊆ N by [ (f * g)(S) = [T ⊆ S] f(T) g(S T),,]where addition and multiplication is carried out in an arbitrary ring. Via Mobius transform and inversion, our algorithm evaluates the subset convolution in O(n2 2n) additions and multiplications, substanti y improving upon the straightforward O(3n) algorithm. Specifically, if the input functions have aninteger range [-M,-M+1,...,M], their subset convolution over the ordinary sum--product ring can be computed in O(2n log M) time; the notation O suppresses polylogarithmic factors.Furthermore, using a standard embedding technique we can compute the subset convolution over the max--sum or min--sum semiring in O(2n M) time. To demonstrate the applicability of fast subset convolution, wepresent the first O(2k n2 + n m) algorithm for the Steiner tree problem in graphs with n vertices, k terminals, and m edges with bounded integer weights, improving upon the O(3kn + 2k n2 + n m) time bound of the classical Dreyfus-Wagner algorithm. We also discuss extensions to recent O(2n)-time algorithms for covering and partitioning problems (Bjorklund and Husfeldt, FOCS 2006; Koivisto, FOCS 2006).
  @cite_23: Given a set @math with @math elements and a family @math of subsets, we show how to partition @math into @math such subsets in @math time. We also consider variations of this problem where the subsets may overlap or are weighted, and we solve the decision, counting, summation, and optimization versions of these problems. Our algorithms are based on the principle of inclusion-exclusion and the zeta transform. In effect we get exact algorithms in @math time for several well-studied partition problems including domatic number, chromatic number, maximum @math -cut, bin packing, list coloring, and the chromatic polynomial. We also have applications to Bayesian learning with decision graphs and to model-based data clustering. If only polynomial space is available, our algorithms run in time @math if membership in @math can be decided in polynomial time. We solve chromatic number in @math time and domatic number in @math time. Finally, we present a family of polynomial space approximation algorithms that find a number between @math and @math in time @math .
summary: Concerning set packings the situation is analogous, albeit the research has been somewhat less extensive. Deciding whether a given family of @math subsets of an @math -element universe contains a @math -packing is known to be W[1]-hard @cite_5 , and thus it is unlikely that the problem is fixed parameter tractable, that is, solvable in time @math for some function @math and constant @math . If @math is fairly large, say exponential in @math , the fastest known algorithms actually count the packings by employing the inclusion--exclusion machinery @cite_23 @cite_3 and run in time @math . This bound holds also for the presented algorithm (cf. Theorem ).