Trimmed Moebius Inversion and Graphs of Bounded Degree
| dc.creator | Björklund, Andreas | |
| dc.creator | Husfeldt, Thore | |
| dc.creator | Kaski, Petteri | |
| dc.creator | Koivisto, Mikko | |
| dc.date | 2008-02-20 | |
| dc.date.accessioned | 2026-07-07T09:22:00Z | |
| dc.date.available | 2026-07-07T09:22:00Z | |
| dc.description | 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$. | |
| dc.identifier | https://arxiv.org/abs/0802.2834 | |
| dc.identifier | http://arxiv.org/abs/0802.2834 | |
| dc.identifier | Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (2008) | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/155226 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Combinatorics | |
| dc.title | Trimmed Moebius Inversion and Graphs of Bounded Degree | |
| dc.type | text |