Inclusion-exclusion algorithms for counting set partitions

Andreas Björklund; Thore Husfeldt

doi:10.1109/FOCS.2006.41

Inclusion-exclusion algorithms for counting set partitions

Andreas Björklund, Thore Husfeldt

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

Abstract

Given a set U with n elements and a family of subsets S ⊆ 2U we show how to count the number of k-partitions S1 ∪ ... ∪ Sk = U into subsets Si ∈ S in time 2nnO(1). The only assumption on S is that it can be enumerated in time 2nnO(1). In effect we get exact algorithms in time 2nnO(1) 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 3nnO(1) if membership in S can be decided in polynomial time. For chromatic number, we present a version that runs in time O(2.2461n) and polynomial space. For domatic number, we present a version that runs in time O(2.8718n). Finally, we present a family of polynomial space approximation algorithms that find a number between χ(G) and [(1 + ϵ)χ(G)] in time O(1.2209n + 2.2461e-ϵn)

Original language	English
Title of host publication	2006 47th Annual IEEE Conference on Foundations of Computer Science
Publisher	IEEE - Institute of Electrical and Electronics Engineers Inc.
Pages	575-582
Number of pages	8
ISBN (Print)	0-7695-2720-5
DOIs	https://doi.org/10.1109/FOCS.2006.41
Publication status	Published - 2006
Event	2006 47th Annual IEEE Conference on Foundations of Computer Science - Berkeley, CA, United States Duration: 2006 Oct 21 → 2006 Oct 24

Conference

Conference	2006 47th Annual IEEE Conference on Foundations of Computer Science
Country/Territory	United States
City	Berkeley, CA
Period	2006/10/21 → 2006/10/24

Subject classification (UKÄ)

Computer Science

Free keywords

polynomial space approximation
bin packing
Hamiltonian subgraph
bounded component spanning forest
chromatic number
domatic number
inclusion-exclusion algorithm
counting set partition

Access to Document

10.1109/FOCS.2006.41

Cite this

@inproceedings{3e2d99aa87354a5cb45b0737378f3084,

title = "Inclusion-exclusion algorithms for counting set partitions",

abstract = "Given a set U with n elements and a family of subsets S ⊆ 2U we show how to count the number of k-partitions S1 ∪ ... ∪ Sk = U into subsets Si ∈ S in time 2nnO(1). The only assumption on S is that it can be enumerated in time 2nnO(1). In effect we get exact algorithms in time 2nnO(1) 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 3nnO(1) if membership in S can be decided in polynomial time. For chromatic number, we present a version that runs in time O(2.2461n) and polynomial space. For domatic number, we present a version that runs in time O(2.8718n). Finally, we present a family of polynomial space approximation algorithms that find a number between χ(G) and [(1 + ϵ)χ(G)] in time O(1.2209n + 2.2461e-ϵn)",

keywords = "polynomial space approximation, bin packing, Hamiltonian subgraph, bounded component spanning forest, chromatic number, domatic number, inclusion-exclusion algorithm, counting set partition",

author = "Andreas Bj{\"o}rklund and Thore Husfeldt",

year = "2006",

doi = "10.1109/FOCS.2006.41",

language = "English",

isbn = "0-7695-2720-5",

pages = "575--582",

booktitle = "2006 47th Annual IEEE Conference on Foundations of Computer Science",

publisher = "IEEE - Institute of Electrical and Electronics Engineers Inc.",

address = "United States",

note = "2006 47th Annual IEEE Conference on Foundations of Computer Science ; Conference date: 21-10-2006 Through 24-10-2006",

}

Björklund, A & Husfeldt, T 2006, Inclusion-exclusion algorithms for counting set partitions. in 2006 47th Annual IEEE Conference on Foundations of Computer Science. IEEE - Institute of Electrical and Electronics Engineers Inc., pp. 575-582, 2006 47th Annual IEEE Conference on Foundations of Computer Science, Berkeley, CA, United States, 2006/10/21. https://doi.org/10.1109/FOCS.2006.41

TY - GEN

T1 - Inclusion-exclusion algorithms for counting set partitions

AU - Björklund, Andreas

AU - Husfeldt, Thore

PY - 2006

Y1 - 2006

N2 - Given a set U with n elements and a family of subsets S ⊆ 2U we show how to count the number of k-partitions S1 ∪ ... ∪ Sk = U into subsets Si ∈ S in time 2nnO(1). The only assumption on S is that it can be enumerated in time 2nnO(1). In effect we get exact algorithms in time 2nnO(1) 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 3nnO(1) if membership in S can be decided in polynomial time. For chromatic number, we present a version that runs in time O(2.2461n) and polynomial space. For domatic number, we present a version that runs in time O(2.8718n). Finally, we present a family of polynomial space approximation algorithms that find a number between χ(G) and [(1 + ϵ)χ(G)] in time O(1.2209n + 2.2461e-ϵn)

AB - Given a set U with n elements and a family of subsets S ⊆ 2U we show how to count the number of k-partitions S1 ∪ ... ∪ Sk = U into subsets Si ∈ S in time 2nnO(1). The only assumption on S is that it can be enumerated in time 2nnO(1). In effect we get exact algorithms in time 2nnO(1) 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 3nnO(1) if membership in S can be decided in polynomial time. For chromatic number, we present a version that runs in time O(2.2461n) and polynomial space. For domatic number, we present a version that runs in time O(2.8718n). Finally, we present a family of polynomial space approximation algorithms that find a number between χ(G) and [(1 + ϵ)χ(G)] in time O(1.2209n + 2.2461e-ϵn)

KW - polynomial space approximation

KW - bin packing

KW - Hamiltonian subgraph

KW - bounded component spanning forest

KW - chromatic number

KW - domatic number

KW - inclusion-exclusion algorithm

KW - counting set partition

U2 - 10.1109/FOCS.2006.41

DO - 10.1109/FOCS.2006.41

M3 - Paper in conference proceeding

SN - 0-7695-2720-5

SP - 575

EP - 582

BT - 2006 47th Annual IEEE Conference on Foundations of Computer Science

PB - IEEE - Institute of Electrical and Electronics Engineers Inc.

T2 - 2006 47th Annual IEEE Conference on Foundations of Computer Science

Y2 - 21 October 2006 through 24 October 2006

ER -

Inclusion-exclusion algorithms for counting set partitions

Abstract

Conference

Subject classification (UKÄ)

Free keywords

Access to Document

Fingerprint

Cite this