The fast intersection transform with applications to counting paths

Abstract

We present an algorithm for evaluating a linear ``intersection transform'' of a function defined on the lattice of subsets of an $n$-element set. In particular, the algorithm constructs an arithmetic circuit for evaluating the transform in ``down-closure time'' relative to the support of the function and the evaluation domain. As an application, we develop an algorithm that, given as input a digraph with $n$ vertices and bounded integer weights at the edges, counts paths by weight and given length $0\le \ell \le n-1$ in time $O^{\ast }(\exp (n\cdot H(\ell /(2n))))$, where $H(p)=-p\log p-(1-p)\log (1-p)$, and the notation $O^{\ast }(\cdot )$ suppresses a factor polynomial in $n$.

11 pages