Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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 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
and
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
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&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}},
  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}},
}