Advanced

Trimmed moebius inversion and graphs of bounded degree

Björklund, Andreas LU ; Husfeldt, Thore LU ; Kaski, Petteri and Koivisto, Mikko (2008) 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008) In STACS 2008: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science p.85-96
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 F of its subsets, trimmed Moebius inversion allows us to compute the number of parkings, coverings, and partitions of U with k sets from F in time within a polynomial factor (in n) of the number of supersets of the members of 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... (More)
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 F of its subsets, trimmed Moebius inversion allows us to compute the number of parkings, coverings, and partitions of U with k sets from F in time within a polynomial factor (in n) of the number of supersets of the members of 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 A. In particular, we show how to compute the Domatic Number in time within a polynomial factor of (2(Delta+1) - 2)(n/(Delta+1)) and the Chromatic Number in time within a polynomial factor of (2(Delta+1) - Delta - 1)(n/(Delta+1)) For any constant A, these bounds are 0 ((2 - epsilon)(n)) for epsilon > 0 independent of the number of vertices n. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
STACS 2008: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science
pages
85 - 96
publisher
LABRI - Laboratoire Bordelais de Recherche en Informatique
conference name
25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)
external identifiers
  • WOS:000254982900007
  • Scopus:45749123453
project
Exact algorithms
language
English
LU publication?
yes
id
30d892fa-0ade-495a-b193-62e6711efeaa (old id 1407345)
alternative location
http://arxiv.org/pdf/0802.2834v1
date added to LUP
2009-06-02 14:42:22
date last changed
2016-10-13 04:47:39
@misc{30d892fa-0ade-495a-b193-62e6711efeaa,
  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 F of its subsets, trimmed Moebius inversion allows us to compute the number of parkings, coverings, and partitions of U with k sets from F in time within a polynomial factor (in n) of the number of supersets of the members of 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 A. In particular, we show how to compute the Domatic Number in time within a polynomial factor of (2(Delta+1) - 2)(n/(Delta+1)) and the Chromatic Number in time within a polynomial factor of (2(Delta+1) - Delta - 1)(n/(Delta+1)) For any constant A, these bounds are 0 ((2 - epsilon)(n)) for epsilon > 0 independent of the number of vertices n.},
  author       = {Björklund, Andreas and Husfeldt, Thore and Kaski, Petteri and Koivisto, Mikko},
  language     = {eng},
  pages        = {85--96},
  publisher    = {ARRAY(0x78b8690)},
  series       = {STACS 2008: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science},
  title        = {Trimmed moebius inversion and graphs of bounded degree},
  year         = {2008},
}