Set partitioning via inclusion–exclusion

Andreas Björklund, Thore Husfeldt, Mikko Koivisto

    Publikation: Artikel i tidsskrift og konference artikel i tidsskriftTidsskriftartikelForskningpeer review

    Abstract

    Given a set N with n elements and a family F of subsets, we show how to partition N into k such subsets in 2nnO(1) time. We also consider variations of this problem where the subsets may overlap or are weighted, and we solve the decision, counting, summation, and optimization versions of these problems. Our algorithms are based on the principle of inclusion-exclusion and the zeta transform. In effect we get exact algorithms in 2nnO(1) time for several well-studied partition problems including domatic number, chromatic number, maximum k-cut, bin packing, list coloring, and the chromatic polynomial. We also have applications to Bayesian learning with decision graphs and to model-based data clustering. If only polynomial space is available, our algorithms run in time 3 nnO(1) if membership in F can be decided in polynomial time. We solve chromatic number in O(2.2461n) time and domatic number in O(2.8718n) time. Finally, we present a family of polynomial space approximation algorithms that find a number between χ(G) and (1 e+ )χ(G) in time O(1.2209n + 2.2461e−n).
    OriginalsprogEngelsk
    TidsskriftSIAM Journal on Computing
    Vol/bind39
    Udgave nummer2
    Sider (fra-til)546-563
    ISSN0097-5397
    StatusUdgivet - 2009

    Emneord

    • set partition
    • graph coloring
    • exact algorithm
    • zeta transform
    • inclusion-exclusion

    Fingeraftryk

    Dyk ned i forskningsemnerne om 'Set partitioning via inclusion–exclusion'. Sammen danner de et unikt fingeraftryk.

    Citationsformater