Advanced

Inclusion-exclusion algorithms for counting set partitions

Björklund, Andreas LU and Husfeldt, Thore LU (2006) 2006 47th Annual IEEE Conference on Foundations of Computer Science In 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:
author
organization
publishing date
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
in
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
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
2007-11-24 09:27:06
date last changed
2017-02-19 04:31:35
@inproceedings{3e2d99aa-8735-4a5c-b45b-0737378f3084,
  abstract     = {Given a set U with n elements and a family of subsets S ⊆ 2&lt;sup&gt;U&lt;/sup&gt; we show how to count the number of k-partitions S&lt;sub&gt;1&lt;/sub&gt; ∪ ... ∪ S&lt;sub&gt;k&lt;/sub&gt; = U into subsets S&lt;sub&gt;i&lt;/sub&gt; ∈ S in time 2&lt;sup&gt;n&lt;/sup&gt;n&lt;sup&gt;O(1)&lt;/sup&gt;. The only assumption on S is that it can be enumerated in time 2&lt;sup&gt;n&lt;/sup&gt;n&lt;sup&gt;O(1)&lt;/sup&gt;. In effect we get exact algorithms in time 2&lt;sup&gt;n&lt;/sup&gt;n&lt;sup&gt;O(1)&lt;/sup&gt; 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&lt;sup&gt;n&lt;/sup&gt;n&lt;sup&gt;O(1)&lt;/sup&gt; if membership in S can be decided in polynomial time. For chromatic number, we present a version that runs in time O(2.2461&lt;sup&gt;n&lt;/sup&gt;) and polynomial space. For domatic number, we present a version that runs in time O(2.8718&lt;sup&gt;n&lt;/sup&gt;). Finally, we present a family of polynomial space approximation algorithms that find a number between χ(G) and [(1 + ϵ)χ(G)] in time O(1.2209&lt;sup&gt;n&lt;/sup&gt; + 2.2461&lt;sup&gt;e-ϵ&lt;/sup&gt;n)},
  author       = {Björklund, Andreas and Husfeldt, Thore},
  booktitle    = {2006 47th Annual IEEE Conference on Foundations of Computer Science},
  isbn         = {0-7695-2720-5},
  keyword      = {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},
  year         = {2006},
}