Björklund, Andreas ;
Husfeldt, Thore ;
Kaski, Petteri ;
Koivisto, Mikko
Trimmed Moebius Inversion and Graphs of Bounded Degree
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 $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 wellstudied
combinatorial optimisation problems on graphs of maximum degree
$Delta$. In particular, we show how to compute the Domatic Number
in time within a polynomial factor of
$(2^{Delta+12)^{n/(Delta+1)$ and the Chromatic Number in time
within a polynomial factor of
$(2^{Delta+1Delta1)^{n/(Delta+1)$. For any constant $Delta$,
these bounds are $O bigl((2epsilon)^n bigr)$ for $epsilon>0$
independent of the number of vertices $n$.
BibTeX  Entry
@InProceedings{bjrklund_et_al:LIPIcs:2008:1336,
author = {Andreas Bj{\"o}rklund and Thore Husfeldt and Petteri Kaski and Mikko Koivisto},
title = {{Trimmed Moebius Inversion and Graphs of Bounded Degree}},
booktitle = {25th International Symposium on Theoretical Aspects of Computer Science},
pages = {8596},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897064},
ISSN = {18688969},
year = {2008},
volume = {1},
editor = {Susanne Albers and Pascal Weil},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1336},
URN = {urn:nbn:de:0030drops13369},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1336},
annote = {Keywords: }
}
Seminar: 

25th International Symposium on Theoretical Aspects of Computer Science

Issue date: 

2008 
Date of publication: 

2008 