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_18: 
  @cite_21: We study ways to expedite Yates’s algorithm for computing the zeta and Moebius transforms of a function defined on the subset lattice. We develop a trimmed variant of Moebius inversion that proceeds point by point, finishing the calculation at a subset before considering its supersets. For an n-element universe U and a family ℱ of its subsets, trimmed Moebius inversion allows us to compute the number of packings, coverings, and partitions of U with k sets from ℱ in time within a polynomial factor (in n) of the number of supersets of the members of ℱ. Relying on an projection theorem of (J. Comb. Theory Ser. A 43:23–37, 1986) to bound the sizes of set families, we apply these ideas to well-studied combinatorial optimisation problems on graphs with maximum degree Δ. In particular, we show how to compute the domatic number in time within a polynomial factor of (2Δ+1−2) n (Δ+1) and the chromatic number in time within a polynomial factor of (2Δ+1−Δ−1) n (Δ+1). For any constant Δ, these bounds are O((2−e) n ) for e>0 independent of the number of vertices n.
  @cite_6: 
  @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 .
  @cite_10: One way to cope with an NP-hard problem is to find an algorithm that is fact on average with respect to a natural probability distribution on inputs. We consider from that point of view the Hamilto...
  @cite_20: Improved randomized and deterministic algorithms are presented for PATH, MATCHING, and PACKING problems. Our randomized algorithms are based on the divide-and-conquer technique, and improve previous best algorithms for these problems. For example, for the k-PATH problem, our randomized algorithm runs in time O(4kk3.42m) and space O(nklogk + m), improving the previous best randomized algorithm for the problem that runs in time O(5.44kkm) and space O(2kkn + m). To achieve improved deterministic algorithms, we study a number of previously proposed de-randomization schemes, and also develop a new derandomization scheme. These studies result in a number of deterministic algorithms: one of time O(4k+o(k)m) for the k-PATH problem, one of time O(2.803kk nlog2 n) for the 3-D MATCHING problem, and one of time O(43k+o(k)n) for the 3-SET PACKING problem. All these significantly improve previous best algorithms for the problems.
summary: The presented meet-in-the-middle approach resembles the randomized divide-and-conquer technique by Chen, Lu, Sze, and Zhang @cite_20 and the similar divide-and-color method by Kneis, M " o lle, Richter, and Rossmanith @cite_6 , designed for parameterized decision problems. These can, in turn, be viewed as extensions of the recursive partitioning technique of Gurevich and Shelah @cite_10 for the Hamiltonian Path problem. That said, our contribution is rather in the observation that, in the counting context, the join operation can be done efficiently using the inclusion--exclusion machinery. While our formalization of the problem as the Disjoint Sum problem is new, the solution itself can, in essence, already be found in Kennes @cite_18 , even though in terms of possibility calculus and without the idea of trimming,'' that is, restricting the computations to small subsets. Kennes's results were rediscovered in a dual form and extended to accommodate trimming in the authors' recent works @cite_23 @cite_3 @cite_21 .