Trimmed Moebius Inversion and Graphs of Bounded Degree

• DOI: 10.1007/s00224-009-9185-7
• Publication Date: 2009-01-28T19:37:56Z
• Authors: Andreas Björklund; Thore Husfeldt; Petteri Kaski; Mikko Koivisto
• Keywords: Degree (music)

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 $\scr F$ of its subsets, trimmed Moebius inversion allows us to compute the number of packings, coverings, and partitions of $U$ with $k$ sets from $\scr F$ in time within a polynomial factor (in $n$) of the number of supersets of the members of $\scr F$. Relying on an intersection theorem of Chung et al. (1986) to bound the sizes of set families, we apply these ideas to well-studied combinatorial optimisation problems on graphs of 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\bigl((2-��)^n\bigr)$ for $��>0$ independent of the number of vertices $n$.