Counting Paths and Packings in Halves

Andreas Björklund, Thore Husfeldt, Petteri Kaski +1

It is shown that one can count $k$-edge paths in an $n$-vertex graph and $m$-set $k$-packings on an $n$-element universe, respectively, in time $\left(\genfrac{}{}{0ex}{}{n}{k/2}\right)$ and ${n \choose mk…