Inclusion-exclusion algorithms for counting set partitions
(2006) 2006 47th Annual IEEE Conference on Foundations of Computer Science p.575-582- 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 k-partitions 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 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... (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 k-partitions 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 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<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, inclusion-exclusion 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
- 2006-10-21 - 2006-10-24
- external identifiers
-
- wos:000242526200055
- scopus:35448988064
- ISBN
- 0-7695-2720-5
- DOI
- 10.1109/FOCS.2006.41
- language
- English
- LU publication?
- yes
- id
- 3e2d99aa-8735-4a5c-b45b-0737378f3084 (old id 617026)
- date added to LUP
- 2016-04-04 11:47:36
- date last changed
- 2022-01-29 22:25:46
@inproceedings{3e2d99aa-8735-4a5c-b45b-0737378f3084,
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 k-partitions 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 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<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 = {{0-7695-2720-5}},
keywords = {{polynomial space approximation; bin packing; Hamiltonian subgraph; bounded component spanning forest; chromatic number; domatic number; inclusion-exclusion algorithm; counting set partition}},
language = {{eng}},
pages = {{575--582}},
publisher = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
title = {{Inclusion-exclusion algorithms for counting set partitions}},
url = {{http://dx.doi.org/10.1109/FOCS.2006.41}},
doi = {{10.1109/FOCS.2006.41}},
year = {{2006}},
}