Advanced

Set partitioning via inclusion-exclusion

Björklund, Andreas LU ; Husfeldt, Thore LU and Koivisto, Mikko (2009) In SIAM Journal on Computing 39(2). p.546-563
Abstract
Given a set N with n elements and a family F of subsets, we show how to partition N into k such subsets in 2(n) n(O)(1) time. We also consider variations of this problem where the subsets may overlap or are weighted, and we solve the decision, counting, summation, and optimization versions of these problems. Our algorithms are based on the principle of inclusion-exclusion and the zeta transform. In effect we get exact algorithms in 2(n) n(O)(1) time for several well-studied partition problems including domatic number, chromatic number, maximum k-cut, bin packing, list coloring, and the chromatic polynomial. We also have applications to Bayesian learning with decision graphs and to model-based data clustering. If only polynomial space is... (More)
Given a set N with n elements and a family F of subsets, we show how to partition N into k such subsets in 2(n) n(O)(1) time. We also consider variations of this problem where the subsets may overlap or are weighted, and we solve the decision, counting, summation, and optimization versions of these problems. Our algorithms are based on the principle of inclusion-exclusion and the zeta transform. In effect we get exact algorithms in 2(n) n(O)(1) time for several well-studied partition problems including domatic number, chromatic number, maximum k-cut, bin packing, list coloring, and the chromatic polynomial. We also have applications to Bayesian learning with decision graphs and to model-based data clustering. If only polynomial space is available, our algorithms run in time 3(n) n(O)(1) if membership in F can be decided in polynomial time. We solve chromatic number in O(2.2461(n)) time and domatic number in O(2.8718(n)) time. Finally, we present a family of polynomial space approximation algorithms that find a number between chi(G) and inverted right perpendicular(1 + epsilon)chi(G)inverted left perpendicular in time O(1.2209(n) + 2.2461(e-epsilon n)). (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
exact algorithm, set partition, inclusion-exclusion, graph coloring, zeta transform
in
SIAM Journal on Computing
volume
39
issue
2
pages
546 - 563
publisher
SIAM Publications
external identifiers
  • wos:000268859000010
ISSN
0097-5397
DOI
10.1137/070683933
project
Exact algorithms
language
English
LU publication?
yes
id
0d9a4ec7-978f-44e2-af82-d188b1d99440 (old id 1477512)
date added to LUP
2009-09-22 15:29:49
date last changed
2016-04-15 21:34:14
@article{0d9a4ec7-978f-44e2-af82-d188b1d99440,
  abstract     = {Given a set N with n elements and a family F of subsets, we show how to partition N into k such subsets in 2(n) n(O)(1) time. We also consider variations of this problem where the subsets may overlap or are weighted, and we solve the decision, counting, summation, and optimization versions of these problems. Our algorithms are based on the principle of inclusion-exclusion and the zeta transform. In effect we get exact algorithms in 2(n) n(O)(1) time for several well-studied partition problems including domatic number, chromatic number, maximum k-cut, bin packing, list coloring, and the chromatic polynomial. We also have applications to Bayesian learning with decision graphs and to model-based data clustering. If only polynomial space is available, our algorithms run in time 3(n) n(O)(1) if membership in F can be decided in polynomial time. We solve chromatic number in O(2.2461(n)) time and domatic number in O(2.8718(n)) time. Finally, we present a family of polynomial space approximation algorithms that find a number between chi(G) and inverted right perpendicular(1 + epsilon)chi(G)inverted left perpendicular in time O(1.2209(n) + 2.2461(e-epsilon n)).},
  author       = {Björklund, Andreas and Husfeldt, Thore and Koivisto, Mikko},
  issn         = {0097-5397},
  keyword      = {exact algorithm,set partition,inclusion-exclusion,graph coloring,zeta transform},
  language     = {eng},
  number       = {2},
  pages        = {546--563},
  publisher    = {SIAM Publications},
  series       = {SIAM Journal on Computing},
  title        = {Set partitioning via inclusion-exclusion},
  url          = {http://dx.doi.org/10.1137/070683933},
  volume       = {39},
  year         = {2009},
}