Set partitioning via inclusionexclusion
(2009) In SIAM Journal on Computing 39(2). p.546563 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 inclusionexclusion and the zeta transform. In effect we get exact algorithms in 2(n) n(O)(1) time for several wellstudied partition problems including domatic number, chromatic number, maximum kcut, bin packing, list coloring, and the chromatic polynomial. We also have applications to Bayesian learning with decision graphs and to modelbased 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 inclusionexclusion and the zeta transform. In effect we get exact algorithms in 2(n) n(O)(1) time for several wellstudied partition problems including domatic number, chromatic number, maximum kcut, bin packing, list coloring, and the chromatic polynomial. We also have applications to Bayesian learning with decision graphs and to modelbased 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(eepsilon n)). (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1477512
 author
 Björklund, Andreas ^{LU} ; Husfeldt, Thore ^{LU} and Koivisto, Mikko
 organization
 publishing date
 2009
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 exact algorithm, set partition, inclusionexclusion, graph coloring, zeta transform
 in
 SIAM Journal on Computing
 volume
 39
 issue
 2
 pages
 546  563
 publisher
 SIAM Publications
 external identifiers

 wos:000268859000010
 ISSN
 00975397
 DOI
 10.1137/070683933
 project
 Exact algorithms
 language
 English
 LU publication?
 yes
 id
 0d9a4ec7978f44e2af82d188b1d99440 (old id 1477512)
 date added to LUP
 20090922 15:29:49
 date last changed
 20160415 21:34:14
@article{0d9a4ec7978f44e2af82d188b1d99440, 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 inclusionexclusion and the zeta transform. In effect we get exact algorithms in 2(n) n(O)(1) time for several wellstudied partition problems including domatic number, chromatic number, maximum kcut, bin packing, list coloring, and the chromatic polynomial. We also have applications to Bayesian learning with decision graphs and to modelbased 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(eepsilon n)).}, author = {Björklund, Andreas and Husfeldt, Thore and Koivisto, Mikko}, issn = {00975397}, keyword = {exact algorithm,set partition,inclusionexclusion,graph coloring,zeta transform}, language = {eng}, number = {2}, pages = {546563}, publisher = {SIAM Publications}, series = {SIAM Journal on Computing}, title = {Set partitioning via inclusionexclusion}, url = {http://dx.doi.org/10.1137/070683933}, volume = {39}, year = {2009}, }