Inclusion-exclusion algorithms for counting set partitions

Summary, in English

Given a set U with n elements and a family of subsets S ⊆ 2^U we show how to count the number of k-partitions S₁ ∪ ... ∪ S_k = U into subsets S_i ∈ S in time 2ⁿn^O(1). The only assumption on S is that it can be enumerated in time 2ⁿn^O(1). In effect we get exact algorithms in time 2ⁿn^O(1) for several well-studied partition problems including domatic number, chromatic number, bounded component spanning forest, partition into Hamiltonian subgraphs, and bin packing. If only polynomial space is available, our algorithms run in time 3ⁿn^O(1) if membership in S can be decided in polynomial time. For chromatic number, we present a version that runs in time O(2.2461ⁿ) and polynomial space. For domatic number, we present a version that runs in time O(2.8718ⁿ). Finally, we present a family of polynomial space approximation algorithms that find a number between χ(G) and [(1 + ϵ)χ(G)] in time O(1.2209ⁿ + 2.2461^e-ϵn)

• Author: Andreas Björklund; Thore Husfeldt
• Department/s: Department of Computer Science; Computer Science; Parallel Systems
• Publishing year: 2006
• Language: English
• Pages: 575-582
• Publication/Series: 2006 47th Annual IEEE Conference on Foundations of Computer Science
• Links: http://dx.doi.org/10.1109/FOCS.2006.41
• Document type: Conference paper
• Publisher: IEEE - Institute of Electrical and Electronics Engineers Inc.
• Topic: Computer Science
• Keywords: polynomial space approximation; bin packing; Hamiltonian subgraph; bounded component spanning forest; chromatic number; domatic number; inclusion-exclusion algorithm; counting set partition
• Conference name: 2006 47th Annual IEEE Conference on Foundations of Computer Science
• Conference date: 2006-10-21 - 2006-10-24
• Conference place: Berkeley, CA, United States
• Status: Published
• ISBN/ISSN/Other: ISBN: 0-7695-2720-5