Inclusionexclusion algorithms for counting set partitions
(2006) 2006 47th Annual IEEE Conference on Foundations of Computer Science p.575582 Abstract
 Given a set U with n elements and a family of subsets S ⊆ 2<sup>U</sup> we show how to count the number of kpartitions S<sub>1</sub> ∪ ... ∪ S<sub>k</sub> = U into subsets S<sub>i</sub> ∈ S in time 2<sup>n</sup>n<sup>O(1)</sup>. The only assumption on S is that it can be enumerated in time 2<sup>n</sup>n<sup>O(1)</sup>. In effect we get exact algorithms in time 2<sup>n</sup>n<sup>O(1)</sup> for several wellstudied 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... (More)
 Given a set U with n elements and a family of subsets S ⊆ 2<sup>U</sup> we show how to count the number of kpartitions S<sub>1</sub> ∪ ... ∪ S<sub>k</sub> = U into subsets S<sub>i</sub> ∈ S in time 2<sup>n</sup>n<sup>O(1)</sup>. The only assumption on S is that it can be enumerated in time 2<sup>n</sup>n<sup>O(1)</sup>. In effect we get exact algorithms in time 2<sup>n</sup>n<sup>O(1)</sup> for several wellstudied 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<sup>n</sup>n<sup>O(1)</sup> if membership in S can be decided in polynomial time. For chromatic number, we present a version that runs in time O(2.2461<sup>n</sup>) and polynomial space. For domatic number, we present a version that runs in time O(2.8718<sup>n</sup>). Finally, we present a family of polynomial space approximation algorithms that find a number between χ(G) and [(1 + ϵ)χ(G)] in time O(1.2209<sup>n</sup> + 2.2461<sup>eϵ</sup>n) (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/617026
 author
 Björklund, Andreas ^{LU} and Husfeldt, Thore ^{LU}
 organization
 publishing date
 2006
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 polynomial space approximation, bin packing, Hamiltonian subgraph, bounded component spanning forest, chromatic number, domatic number, inclusionexclusion algorithm, counting set partition
 host publication
 2006 47th Annual IEEE Conference on Foundations of Computer Science
 pages
 8 pages
 publisher
 IEEE  Institute of Electrical and Electronics Engineers Inc.
 conference name
 2006 47th Annual IEEE Conference on Foundations of Computer Science
 conference location
 Berkeley, CA, United States
 conference dates
 20061021  20061024
 external identifiers

 wos:000242526200055
 scopus:35448988064
 ISBN
 0769527205
 DOI
 10.1109/FOCS.2006.41
 language
 English
 LU publication?
 yes
 id
 3e2d99aa87354a5cb45b0737378f3084 (old id 617026)
 date added to LUP
 20160404 11:47:36
 date last changed
 20211006 02:54:41
@inproceedings{3e2d99aa87354a5cb45b0737378f3084, abstract = {Given a set U with n elements and a family of subsets S ⊆ 2<sup>U</sup> we show how to count the number of kpartitions S<sub>1</sub> ∪ ... ∪ S<sub>k</sub> = U into subsets S<sub>i</sub> ∈ S in time 2<sup>n</sup>n<sup>O(1)</sup>. The only assumption on S is that it can be enumerated in time 2<sup>n</sup>n<sup>O(1)</sup>. In effect we get exact algorithms in time 2<sup>n</sup>n<sup>O(1)</sup> for several wellstudied 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<sup>n</sup>n<sup>O(1)</sup> if membership in S can be decided in polynomial time. For chromatic number, we present a version that runs in time O(2.2461<sup>n</sup>) and polynomial space. For domatic number, we present a version that runs in time O(2.8718<sup>n</sup>). Finally, we present a family of polynomial space approximation algorithms that find a number between χ(G) and [(1 + ϵ)χ(G)] in time O(1.2209<sup>n</sup> + 2.2461<sup>eϵ</sup>n)}, author = {Björklund, Andreas and Husfeldt, Thore}, booktitle = {2006 47th Annual IEEE Conference on Foundations of Computer Science}, isbn = {0769527205}, language = {eng}, pages = {575582}, publisher = {IEEE  Institute of Electrical and Electronics Engineers Inc.}, title = {Inclusionexclusion algorithms for counting set partitions}, url = {http://dx.doi.org/10.1109/FOCS.2006.41}, doi = {10.1109/FOCS.2006.41}, year = {2006}, }