Trimmed Moebius Inversion and Graphs of Bounded Degree
- Andreas Björklund,
- ,
- Petter Kaski,
- Mikko Koivisto
- Lund University,
- Aalto University,
- University of Helsinki
Publikation:
Artikel i tidsskrift og konference artikel i tidsskrift
Tidsskriftartikel
Forskning
Peer-reviewResume
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.
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.
Publikation information
Produktionstype
Publikation:
Artikel i tidsskrift og konference artikel i tidsskrift
Tidsskriftartikel
Forskning
Peer-reviewOriginalsprog
EngelskSider fra-til (Antal sider)
Sider 637-654Tidsskrift (Bind, Nummer)
Theory of Computing Systems (Bind 47, Udgave 3)Publikationsmilepæle
- Udgivet - 2010
Publikationsstatus
Udgivet - 2010
ISSN
1432-4350Publikations IDer
- Scopus: 77953322721
Metrikker
PlumX
Hentninger
15
Antal citationer
40
