47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) Inclusion--Exclusion Algorithms for Counting Set Partitions Berkeley, California October 21-October 24 ISBN: 0-7695-2720-5
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.41
Given a set U with n elements and a family of subsets S \subseteq 2^U we show how to count the number of k-partitions S_1 \cup ? ? ? \cup S_k = U into subsets S_i \in S in time 2^{n}n^{O(1)}. The only assumption on S is that it can be enumerated in time 2^{n}n^{O(1)}. In effect we get exact algorithms in time 2^{n}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}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^n ) and polynomial space. For Domatic Number, we present a version that runs in time O(2.8718^n ). Finally, we present a family of polynomial space approximation algorithms that find a number between \chi \left( G \right) and \left\lceil {\left( {1 + \in } \right)\chi \left( G \right)} \right\rceil in time O(1.2209^n + 2.2461^{e^{-\in}n ).
Citation:
Andreas Bjorklund, Thore Husfeldt, "Inclusion--Exclusion Algorithms for Counting Set Partitions," focs, pp.575-582, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb