## Abstract

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 Chung et al. (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

Relying on an projection theorem of Chung et al. (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−ε)^{n}) for ε>0 independent of the number of vertices n.Original language | English |
---|---|

Journal | Theory of Computing Systems |

Volume | 47 |

Issue number | 3 |

Pages (from-to) | 637-654 |

ISSN | 1432-4350 |

Publication status | Published - 2010 |

## Keywords

- Graph algorithms
- Inclusion-exclusion
- Chromatic number
- Domatic number