The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Set partitioning via inclusion-exclusion

På svenska

Author

Summary, in English

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)).

Publishing year

2009

Language

English

Pages

546-563

Publication/Series

SIAM Journal on Computing

Volume

39

Issue

2

Document type

Journal article

Publisher

Society for Industrial and Applied Mathematics

Topic

  • Computer Science

Keywords

  • exact algorithm
  • set partition
  • inclusion-exclusion
  • graph coloring
  • zeta transform

Status

Published

Project

  • Exact algorithms

Research group

  • Algorithms

ISBN/ISSN/Other

  • ISSN: 0097-5397