# Reconstructing Set Partitions

1 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We study the following combinatorial search problem: Reconstruct an unknown partition of the set [n]={1,...,n} into at most K disjoint non-empty subsets (classes) by making queries about subsets $Q_i \subseteq [n]$ such that the query returns the number of classes represented in $Q_i$. The goal is to reconstruct the whole partition with as few queries as possible. We also consider a variant of the problem where a representative of each class should be found without necessarily reconstructing the whole partition. Besides its theoretical interest, the problem has practical applications. Paper \cite{SBAW-RECOMB97} considers a physical mapping method based on hybridizing probes to chromosomes using the FISH technology. Under some reasonable assumptions, the method amounts to finding a partition of probes determined by the chromosome they hybridize to, and actually corresponds to the above formalization.
Keywords :
Document type :
Conference papers
Domain :

https://hal.inria.fr/inria-00098744
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 8:32:28 AM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM
Long-term archiving on: : Wednesday, March 29, 2017 - 12:41:52 PM

### Identifiers

• HAL Id : inria-00098744, version 1

### Citation

Vladimir Grebinski, Gregory Kucherov. Reconstructing Set Partitions. Tenth Annual ACM-SIAM Symposium on Discrete Algorithms - SODA'99, 1999, Baltimore, Maryland/US, pp.2. ⟨inria-00098744⟩

Record views