Trimmed Moebius Inversion and Graphs of Bounded Degree

Andreas Björklund, Thore Husfeldt, Petter Kaski, Mikko Koivisto

Publikation: Artikel i tidsskrift og konference artikel i tidsskriftTidsskriftartikelForskningpeer review

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 Δ+12)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.
OriginalsprogEngelsk
TidsskriftTheory of Computing Systems
Vol/bind47
Udgave nummer3
Sider (fra-til) 637-654
ISSN1432-4350
StatusUdgivet - 2010

Emneord

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

Fingeraftryk

Dyk ned i forskningsemnerne om 'Trimmed Moebius Inversion and Graphs of Bounded Degree'. Sammen danner de et unikt fingeraftryk.

Citationsformater