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